



"""simple docstring"""





from __future__ import annotations

from typing import Any




class       lowercase__      :
							'''simple docstring'''







							def __init__(	self						,							snake_case    )      ->				Dict:
									_UpperCAmelCase							=		num_of_nodes
									_UpperCAmelCase							=		[]
									_UpperCAmelCase							=		{}






							def 							lowerCamelCase_ (	self						,							snake_case						,							snake_case						,							snake_case    )      ->				Optional[int]:
									self.m_edges.append([u_node, v_node, weight]    )






							def 							lowerCamelCase_ (	self						,							snake_case    )      ->				Optional[int]:

									if self.m_component[u_node] == u_node:
											return u_node
									return self.find_component(self.m_component[u_node]    )






							def 							lowerCamelCase_ (	self						,							snake_case    )      ->				int:

									if self.m_component[u_node] != u_node:
											for k in self.m_component:
													_UpperCAmelCase							=		self.find_component(__lowerCAmelCase    )






							def 							lowerCamelCase_ (	self						,							snake_case						,							snake_case						,							snake_case    )      ->				int:

									if component_size[u_node] <= component_size[v_node]:
											_UpperCAmelCase							=		v_node
											component_size[v_node] += component_size[u_node]
											self.set_component(__lowerCAmelCase    )

									elif component_size[u_node] >= component_size[v_node]:
											_UpperCAmelCase							=		self.find_component(__lowerCAmelCase    )
											component_size[u_node] += component_size[v_node]
											self.set_component(__lowerCAmelCase    )






							def 							lowerCamelCase_ (	self    )      ->				Union[str, Any]:
									_UpperCAmelCase							=		[]
									_UpperCAmelCase							=		0

									_UpperCAmelCase							=		[-1] * self.m_num_of_nodes

									# A list of components (initialized to all of the nodes)
									for node in range(self.m_num_of_nodes    ):
											self.m_component.update({node: node}    )
											component_size.append(1    )

									_UpperCAmelCase							=		self.m_num_of_nodes

									while num_of_components > 1:
											for edge in self.m_edges:
													_UpperCAmelCase							=		edge

													_UpperCAmelCase							=		self.m_component[u]
													_UpperCAmelCase							=		self.m_component[v]

													if u_component != v_component:

															for component in (u_component, v_component):
																	if (
																	    minimum_weight_edge[component] == -1
																	    or minimum_weight_edge[component][2] > w
																	):
																			_UpperCAmelCase							=		[u, v, w]

											for edge in minimum_weight_edge:
													if isinstance(__lowerCAmelCase						,							__lowerCAmelCase    ):
															_UpperCAmelCase							=		edge

															_UpperCAmelCase							=		self.m_component[u]
															_UpperCAmelCase							=		self.m_component[v]

															if u_component != v_component:
																	mst_weight += w
																	self.union(__lowerCAmelCase						,							__lowerCAmelCase						,							__lowerCAmelCase    )
																	print(f'Added edge [{u} - {v}]\nAdded weight: {w}\n'    )
																	num_of_components -= 1

											_UpperCAmelCase							=		[-1] * self.m_num_of_nodes
									print(f'The total weight of the minimal spanning tree is: {mst_weight}'    )







def 						UpperCAmelCase  (		):

		'''simple docstring'''





if __name__ == "__main__":
					import doctest

					doctest.testmod()










'''simple docstring'''

UpperCamelCase      					="Input must be a string of 8 numbers plus letter"
UpperCamelCase      					="TRWAGMYFPDXBNJZSQVHLCKE"



def 				snake_case       (  a_				:			str						)							->					bool:





      """simple docstring"""

      if not isinstance(a_     , a_						):
            UpperCamelCase_					: List[str]            =				f"Expected string as input, found {type(a_						).__name__}"
            raise TypeError(a_						)

      UpperCamelCase_					: int            =				spanish_id.replace("""-"""     , """"""						).upper()
      if len(a_						) != 9:
            raise ValueError(a_						)

      try:
            UpperCamelCase_					: List[str]            =				int(spanish_id_clean[0:8]						)
            UpperCamelCase_					: Any            =				spanish_id_clean[8]
      except ValueError as ex:
            raise ValueError(a_						) from ex

      if letter.isdigit():
            raise ValueError(a_						)

      return letter == LOOKUP_LETTERS[number % 23]


if __name__ == "__main__":
      import doctest

      doctest.testmod()






