




"""simple docstring"""

from __future__ import annotations

class 							lowercase   :







				def __init__(				self :       List[str]   ,  _lowerCamelCase :       int							):



					"""simple docstring"""

					A_	:					str						 =		vertices
					A_	:					Any						 =		[[0] * vertices for _ in range(_lowerCamelCase							)]







				def        a_	(				self :       str   ,  _lowerCamelCase :       list[int]							):



					"""simple docstring"""

					print('''Vertex \t Distance from Source'''							)
					for vertex in range(self.vertices							):
						print(_lowerCamelCase   ,  '''\t\t'''   ,  distances_from_source[vertex]							)







				def        a_	(				self :       str   ,  _lowerCamelCase :       list[int]   ,  _lowerCamelCase :       list[bool]							):



					"""simple docstring"""

					A_	:					str						 =		1E7
					A_	:					Tuple						 =		0

					# Search not nearest vertex not in the shortest path tree
					for vertex in range(self.vertices							):
						if distances_from_source[vertex] < minimum and visited[vertex] is False:
							A_	:					Optional[int]						 =		distances_from_source[vertex]
							A_	:					Union[str, Any]						 =		vertex
					return min_index







				def        a_	(				self :       Union[str, Any]   ,  _lowerCamelCase :       int							):



					"""simple docstring"""

					A_	:					Optional[Any]						 =		[int(1E7							)] * self.vertices  # distances from the source
					A_	:					List[Any]						 =		0
					A_	:					Any						 =		[False] * self.vertices

					for _ in range(self.vertices							):
						A_	:					List[Any]						 =		self.minimum_distance(_lowerCamelCase   ,  _lowerCamelCase							)
						A_	:					str						 =		True

						# Update dist value of the adjacent vertices
						# of the picked vertex only if the current
						# distance is greater than new distance and
						# the vertex in not in the shortest path tree
						for v in range(self.vertices							):
							if (
							    self.graph[u][v] > 0
							    and visited[v] is False
							    and distances[v] > distances[u] + self.graph[u][v]
							):
								A_	:					Optional[Any]						 =		distances[u] + self.graph[u][v]

					self.print_solution(_lowerCamelCase							)


if __name__ == "__main__":
		_lowerCamelCase	:      Any   =							Graph(9)
		_lowerCamelCase	:      Any   =							[
		    [0, 4, 0, 0, 0, 0, 0, 8, 0],
		    [4, 0, 8, 0, 0, 0, 0, 11, 0],
		    [0, 8, 0, 7, 0, 4, 0, 0, 2],
		    [0, 0, 7, 0, 9, 14, 0, 0, 0],
		    [0, 0, 0, 9, 0, 10, 0, 0, 0],
		    [0, 0, 4, 14, 10, 0, 2, 0, 0],
		    [0, 0, 0, 0, 0, 2, 0, 1, 6],
		    [8, 11, 0, 0, 0, 0, 1, 0, 7],
		    [0, 0, 2, 0, 0, 0, 6, 7, 0],
		]
		graph.dijkstra(0)











"""simple docstring"""

class 							lowercase   :







				def __init__(				self :       Union[str, Any]   ,  _lowerCamelCase :       int							):



					"""simple docstring"""

					A_	:					Optional[int]						 =		data
					A_	:					int
					A_	:					Node

def 		lowercase_   (		_UpperCAmelCase						):




	"""simple docstring"""






	A_	:					List[str]						 =		0
	A_	:					List[str]						 =		x

def 		lowercase_   (		_UpperCAmelCase	,   _UpperCAmelCase						):




	"""simple docstring"""






	A_ ,			A_	:					Any						 =		find_set(_UpperCAmelCase						), find_set(_UpperCAmelCase						)
	if x == y:
		return

	elif x.rank > y.rank:
		A_	:					Optional[int]						 =		x
	else:
		A_	:					Optional[int]						 =		y
		if x.rank == y.rank:
			y.rank += 1

def 		lowercase_   (		_UpperCAmelCase						):




	"""simple docstring"""






	if x != x.parent:
		A_	:					Union[str, Any]						 =		find_set(x.parent						)
	return x.parent

def 		lowercase_   (		_UpperCAmelCase						):




	"""simple docstring"""






	A_	:					str						 =		({0, 1, 2}, {3, 4, 5})
	for s in sets:
		if node.data in s:
			return s
	A_	:					Optional[int]						 =		f"""{node.data} is not in {sets}"""
	raise ValueError(_UpperCAmelCase						)

def 		lowercase_   (		):




	"""simple docstring"""






	A_	:					Dict						 =		[Node(_UpperCAmelCase						) for i in range(6						)]
	for v in vertex:
		make_set(_UpperCAmelCase						)

	union_set(vertex[0]	,   vertex[1]						)
	union_set(vertex[1]	,   vertex[2]						)
	union_set(vertex[3]	,   vertex[4]						)
	union_set(vertex[3]	,   vertex[5]						)

	for nodea in vertex:
		for nodea in vertex:
			if find_python_set(_UpperCAmelCase						).isdisjoint(find_python_set(_UpperCAmelCase						)						):
				assert find_set(_UpperCAmelCase						) != find_set(_UpperCAmelCase						)
			else:
				assert find_set(_UpperCAmelCase						) == find_set(_UpperCAmelCase						)


if __name__ == "__main__":
		test_disjoint_set()





