


from __future__ import annotations

from typing import Any







class        lowerCamelCase__	:






   """simple docstring"""






   def __init__(							self      ,						snake_case     ):

      '''simple docstring'''


      UpperCamelCase__					=       num_of_nodes
      UpperCamelCase__					=       []
      UpperCamelCase__					=       {}




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case      ,						snake_case     ):

      '''simple docstring'''


      self.m_edges.append([u_node, v_node, weight]     )




   def 				snake_case__				(							self      ,						snake_case     ):

      '''simple docstring'''


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




   def 				snake_case__				(							self      ,						snake_case     ):

      '''simple docstring'''


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




   def 				snake_case__				(							self      ,						snake_case      ,						snake_case      ,						snake_case     ):

      '''simple docstring'''


      if component_size[u_node] <= component_size[v_node]:
         UpperCamelCase__					=       v_node
         component_size[v_node] += component_size[u_node]
         self.set_component(snake_case     )

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







   def 				snake_case__				(							self     ):

      '''simple docstring'''


      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__,      UpperCamelCase__,      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(snake_case      ,						snake_case     ):
               UpperCamelCase__,      UpperCamelCase__,      UpperCamelCase__					=       edge

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

               if u_component != v_component:
                  mst_weight += w
                  self.union(snake_case      ,						snake_case      ,						snake_case     )
                  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_(				)->		None:
   pass


if __name__ == "__main__":
      import doctest

      doctest.testmod()






from typing import Any







class        lowerCamelCase__	:






			"""simple docstring"""






			def __init__(							self      ,						snake_case     ):

						'''simple docstring'''


						UpperCamelCase__					=       data
						UpperCamelCase__					=       None







class        lowerCamelCase__	:






			"""simple docstring"""






			def __init__(							self     ):

						'''simple docstring'''


						UpperCamelCase__					=       None




			def 				snake_case__				(							self     ):

						'''simple docstring'''


						UpperCamelCase__					=       self.head
						while temp is not None:
									print(temp.data      ,						end=" "     )
									UpperCamelCase__					=       temp.next
						print()




			def 				snake_case__				(							self      ,						snake_case     ):

						'''simple docstring'''


						UpperCamelCase__					=       Node(snake_case     )
						UpperCamelCase__					=       self.head
						UpperCamelCase__					=       new_node







			def 				snake_case__				(							self      ,						snake_case      ,						snake_case     ):

						'''simple docstring'''


						if node_data_a == node_data_a:
									return
						else:
									UpperCamelCase__					=       self.head
									while node_a is not None and node_a.data != node_data_a:
												UpperCamelCase__					=       node_a.next

									UpperCamelCase__					=       self.head
									while node_a is not None and node_a.data != node_data_a:
												UpperCamelCase__					=       node_a.next

									if node_a is None or node_a is None:
												return

									UpperCamelCase__,      UpperCamelCase__					=       node_a.data, node_a.data


if __name__ == "__main__":
						__UpperCamelCase    		=       LinkedList()
						for i in range(5, 0, -1):
												ll.push(i)

						ll.print_list()

						ll.swap_nodes(1, 4)
						print('After swapping')
						ll.print_list()


