

"""simple docstring"""




from __future__ import annotations

from typing import Any







class      __lowercase			:

  def __init__(  self		:			Optional[Any]					,A		:			Dict    ):






   '''simple docstring'''
   UpperCAmelCase__					:  List[str]					   =					num_of_nodes
   UpperCAmelCase__					:  Union[str, Any]					   =					[]
   UpperCAmelCase__					:  Dict					   =					{}

  def    __lowercase       (  self		:			str					,A		:			Dict					,A		:			Union[str, Any]					,A		:			Any    ):






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

  def    __lowercase       (  self		:			int					,A		:			Dict    ):






   '''simple docstring'''

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

  def    __lowercase       (  self		:			Union[str, Any]					,A		:			Optional[Any]    ):






   '''simple docstring'''

   if self.m_component[u_node] != u_node:
    for k in self.m_component:
     UpperCAmelCase__					:  str					   =					self.find_component(UpperCAmelCase_    )

  def    __lowercase       (  self		:			List[Any]					,A		:			List[Any]					,A		:			Dict					,A		:			int    ):






   '''simple docstring'''

   if component_size[u_node] <= component_size[v_node]:
    UpperCAmelCase__					:  Optional[int]					   =					v_node
    component_size[v_node] += component_size[u_node]
    self.set_component(UpperCAmelCase_    )

   elif component_size[u_node] >= component_size[v_node]:
    UpperCAmelCase__					:  List[str]					   =					self.find_component(UpperCAmelCase_    )
    component_size[u_node] += component_size[v_node]
    self.set_component(UpperCAmelCase_    )




  def    __lowercase       (  self		:			Union[str, Any]    ):






   '''simple docstring'''
   UpperCAmelCase__					:  Dict					   =					[]
   UpperCAmelCase__					:  List[str]					   =					0

   UpperCAmelCase__					:  Union[str, Any]					   =					[-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__					:  List[str]					   =					self.m_num_of_nodes

   while num_of_components > 1:
    for edge in self.m_edges:
     UpperCAmelCase__   ,      UpperCAmelCase__   ,      UpperCAmelCase__					:  Dict					   =					edge

     UpperCAmelCase__					:  int					   =					self.m_component[u]
     UpperCAmelCase__					:  List[Any]					   =					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__					:  Any					   =					[u, v, w]

    for edge in minimum_weight_edge:
     if isinstance(UpperCAmelCase_					,UpperCAmelCase_    ):
      UpperCAmelCase__   ,      UpperCAmelCase__   ,      UpperCAmelCase__					:  int					   =					edge

      UpperCAmelCase__					:  int					   =					self.m_component[u]
      UpperCAmelCase__					:  Tuple					   =					self.m_component[v]

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

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







def   lowerCAmelCase						(					):
 '''simple docstring'''





 pass


if __name__ == "__main__":
      import doctest

      doctest.testmod()








"""simple docstring"""




def   lowerCAmelCase						(					__UpperCamelCase      ):
 '''simple docstring'''





 UpperCAmelCase__					:  str					   =					[]
 if len(__UpperCamelCase      ) == 1:
  return [nums.copy()]
 for _ in range(len(__UpperCamelCase      )      ):
  UpperCAmelCase__					:  Tuple					   =					nums.pop(0      )
  UpperCAmelCase__					:  List[str]					   =					permute(__UpperCamelCase      )
  for perm in permutations:
   perm.append(__UpperCamelCase      )
  result.extend(__UpperCamelCase      )
  nums.append(__UpperCamelCase      )
 return result
def   lowerCAmelCase						(					__UpperCamelCase      ):
 '''simple docstring'''





 def backtrack(__UpperCamelCase      ):
  if start == len(__UpperCamelCase      ) - 1:
   output.append(nums[:]      )
  else:
   for i in range(__UpperCamelCase							,    len(__UpperCamelCase      )      ):
    UpperCAmelCase__   ,      UpperCAmelCase__					:  Union[str, Any]					   =					nums[i], nums[start]
    backtrack(start + 1      )
    UpperCAmelCase__   ,      UpperCAmelCase__					:  Union[str, Any]					   =					nums[i], nums[start]  # backtrack

 UpperCAmelCase__					:  List[str]					   =					[]
 backtrack(0      )
 return output


if __name__ == "__main__":
      import doctest

      # use res to print the data in permute2 function
      __UpperCAmelCase =				permutea([1, 2, 3])
      print(res)
      doctest.testmod()





