






from __future__ import annotations

from typing import Generic, TypeVar

lowerCamelCase      				=     TypeVar('''T''')





class     snake_case_			(				Generic[T]							):


							"""simple docstring"""





							def __init__( self					,						_A							):
												__lowerCAmelCase					=							data
												__lowerCAmelCase					=							self
												__lowerCAmelCase					=							0





class     snake_case_			(				Generic[T]							):


							"""simple docstring"""





							def __init__( self							):
												# map from node name to the node object
												__lowerCAmelCase					=							{}




							def        A__  ( self					,						_A							):
												# create a new set with x as its member
												__lowerCAmelCase					=							DisjointSetTreeNode(_A							)




							def        A__  ( self					,						_A							):
												# find the set x belongs to (with path-compression)
												__lowerCAmelCase					=							self.map[data]
												if elem_ref != elem_ref.parent:
																	__lowerCAmelCase					=							self.find_set(elem_ref.parent.data							)
												return elem_ref.parent




							def        A__  ( self					,						_A					,						_A							):
												# helper function for union operation
												if nodea.rank > nodea.rank:
																	__lowerCAmelCase					=							nodea
												else:
																	__lowerCAmelCase					=							nodea
																	if nodea.rank == nodea.rank:
																						nodea.rank += 1




							def        A__  ( self					,						_A					,						_A							):
												# merge 2 disjoint sets
												self.link(self.find_set(_A							)					,						self.find_set(_A							)							)





class     snake_case_			(				Generic[T]							):


							"""simple docstring"""





							def __init__( self							):
												# connections: map from the node to the neighbouring nodes (with weights)
												__lowerCAmelCase					=							{}




							def        A__  ( self					,						_A							):
												# add a node ONLY if its not present in the graph
												if node not in self.connections:
																	__lowerCAmelCase					=							{}




							def        A__  ( self					,						_A					,						_A					,						_A							):
												# add an edge with the given weight
												self.add_node(_A							)
												self.add_node(_A							)
												__lowerCAmelCase					=							weight
												__lowerCAmelCase					=							weight




							def        A__  ( self							):
												__lowerCAmelCase					=							[]
												__lowerCAmelCase					=							set()
												for start in self.connections:
																	for end in self.connections[start]:
																						if (start, end) not in seen:
																											seen.add((end, start)							)
																											edges.append((start, end, self.connections[start][end])							)
												edges.sort(key=lambda _A							: x[2]							)

												# creating the disjoint set
												__lowerCAmelCase					=							DisjointSetTree[T]()
												for node in self.connections:
																	disjoint_set.make_set(_A							)

												# MST generation
												__lowerCAmelCase					=							0
												__lowerCAmelCase					=							0
												__lowerCAmelCase					=							GraphUndirectedWeighted[T]()
												while num_edges < len(self.connections							) - 1:
																	__lowerCAmelCase,	__lowerCAmelCase,	__lowerCAmelCase					=							edges[index]
																	index += 1
																	__lowerCAmelCase					=							disjoint_set.find_set(_A							)
																	__lowerCAmelCase					=							disjoint_set.find_set(_A							)
																	if parent_u != parent_v:
																						num_edges += 1
																						graph.add_edge(_A					,						_A					,						_A							)
																						disjoint_set.union(_A					,						_A							)
												return graph









from graphs.minimum_spanning_tree_kruskal import kruskal


def        __lowercase    (  ):

					"""simple docstring"""






					__lowerCAmelCase					=							9
					__lowerCAmelCase					=							[
					    [0, 1, 4],
					    [0, 7, 8],
					    [1, 2, 8],
					    [7, 8, 7],
					    [7, 6, 1],
					    [2, 8, 2],
					    [8, 6, 6],
					    [2, 3, 7],
					    [2, 5, 4],
					    [6, 5, 2],
					    [3, 5, 14],
					    [3, 4, 9],
					    [5, 4, 10],
					    [1, 7, 11],
					]

					__lowerCAmelCase					=							kruskal(UpperCAmelCase__		,					UpperCAmelCase__      )

					__lowerCAmelCase					=							[
					    [7, 6, 1],
					    [2, 8, 2],
					    [6, 5, 2],
					    [0, 1, 4],
					    [2, 5, 4],
					    [2, 3, 7],
					    [0, 7, 8],
					    [3, 4, 9],
					]

					assert sorted(UpperCAmelCase__      ) == sorted(UpperCAmelCase__      )






