




'''simple docstring'''





from __future__ import annotations

from typing import Any

class   _a							:






     def __init__(					self   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE = 0       )				->     None:
          _snake_case				,   _snake_case				= row, column
          _snake_case				= [[default_value for c in range(_SCREAMING_SNAKE_CASE       )] for r in range(_SCREAMING_SNAKE_CASE       )]






     def __str__(					self       )				->     str:
          _snake_case				= f"""Matrix consist of {self.row} rows and {self.column} columns\n"""

          # Make string identifier
          _snake_case				= 0
          for row_vector in self.array:
               for obj in row_vector:
                    _snake_case				= max(_SCREAMING_SNAKE_CASE   ,len(str(_SCREAMING_SNAKE_CASE       )       )       )
          _snake_case				= f"""%{max_element_length}s"""

          # Make string and return
          def single_line(_SCREAMING_SNAKE_CASE       ) -> str:
               nonlocal string_format_identifier
               _snake_case				= "["
               line += ", ".join(string_format_identifier % (obj,) for obj in row_vector       )
               line += "]"
               return line

          s += "\n".join(single_line(_SCREAMING_SNAKE_CASE       ) for row_vector in self.array       )
          return s






     def __repr__(					self       )				->     str:
          return str(self       )






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE       )				->     bool:
          if not (isinstance(_SCREAMING_SNAKE_CASE   ,(list, tuple)       ) and len(_SCREAMING_SNAKE_CASE       ) == 2):
               return False
          elif not (0 <= loc[0] < self.row and 0 <= loc[1] < self.column):
               return False
          else:
               return True






     def __getitem__(					self   ,_SCREAMING_SNAKE_CASE       )				->     Any:
          assert self.validate_indicies(_SCREAMING_SNAKE_CASE       )
          return self.array[loc[0]][loc[1]]






     def __setitem__(					self   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )				->     None:
          assert self.validate_indicies(_SCREAMING_SNAKE_CASE       )
          _snake_case				= value






     def __add__(					self   ,_SCREAMING_SNAKE_CASE       )				->     Matrix:
          assert isinstance(_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )
          assert self.row == another.row and self.column == another.column

          # Add
          _snake_case				= Matrix(self.row   ,self.column       )
          for r in range(self.row       ):
               for c in range(self.column       ):
                    _snake_case				= self[r, c] + another[r, c]
          return result






     def __neg__(					self       )				->     Matrix:
          _snake_case				= Matrix(self.row   ,self.column       )
          for r in range(self.row       ):
               for c in range(self.column       ):
                    _snake_case				= -self[r, c]
          return result






     def __sub__(					self   ,_SCREAMING_SNAKE_CASE       )				->     Matrix:
          return self + (-another)






     def __mul__(					self   ,_SCREAMING_SNAKE_CASE       )				->     Matrix:

          if isinstance(_SCREAMING_SNAKE_CASE   ,(int, float)       ):  # Scalar multiplication
               _snake_case				= Matrix(self.row   ,self.column       )
               for r in range(self.row       ):
                    for c in range(self.column       ):
                         _snake_case				= self[r, c] * another
               return result
          elif isinstance(_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       ):  # Matrix multiplication
               assert self.column == another.row
               _snake_case				= Matrix(self.row   ,another.column       )
               for r in range(self.row       ):
                    for c in range(another.column       ):
                         for i in range(self.column       ):
                              result[r, c] += self[r, i] * another[i, c]
               return result
          else:
               _snake_case				= f"""Unsupported type given for another ({type(_SCREAMING_SNAKE_CASE       )})"""
               raise TypeError(_SCREAMING_SNAKE_CASE       )






     def 							_lowercase      (					self       )				->     Matrix:
          _snake_case				= Matrix(self.column   ,self.row       )
          for r in range(self.row       ):
               for c in range(self.column       ):
                    _snake_case				= self[r, c]
          return result






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )				->     Any:
          assert isinstance(_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       ) and isinstance(_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )
          assert self.row == self.column == u.row == v.row  # u, v should be column vector
          assert u.column == v.column == 1  # u, v should be column vector

          # Calculate
          _snake_case				= v.transpose()
          _snake_case				= (v_t * self * u)[0, 0] + 1
          if numerator_factor == 0:
               return None  # It's not invertable
          return self - ((self * u) * (v_t * self) * (1.0 / numerator_factor))


# Testing
if __name__ == "__main__":





   def       __a      (  )		->					None:

        """simple docstring"""




        _snake_case				= Matrix(3   ,		3   ,		0       )
        for i in range(3       ):
             _snake_case				= 1
        print(F"""a^(-1) is {ainv}"""       )
        # u, v
        _snake_case				= Matrix(3   ,		1   ,		0       )
        _snake_case				,   _snake_case				,   _snake_case				= 1, 2, -3
        _snake_case				= Matrix(3   ,		1   ,		0       )
        _snake_case				,   _snake_case				,   _snake_case				= 4, -2, 5
        print(F"""u is {u}"""       )
        print(F"""v is {v}"""       )
        print(F"""uv^T is {u * v.transpose()}"""       )
        # Sherman Morrison
        print(F"""(a + uv^T)^(-1) is {ainv.sherman_morrison(_UpperCamelCase   ,		_UpperCamelCase       )}"""       )





   def       __a      (  )		->					None:

        """simple docstring"""




        import doctest

        doctest.testmod()





   testa()








'''simple docstring'''





from __future__ import annotations

from typing import Any

class   _a							:






     def __init__(					self   ,_SCREAMING_SNAKE_CASE       )				->     None:
          _snake_case				= num_of_nodes
          _snake_case				= []
          _snake_case				= {}






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )				->     None:
          self.m_edges.append([u_node, v_node, weight]       )






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE       )				->     int:

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






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE       )				->     None:

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






     def 							_lowercase      (					self   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       )				->     None:

          if component_size[u_node] <= component_size[v_node]:
               _snake_case				= v_node
               component_size[v_node] += component_size[u_node]
               self.set_component(_SCREAMING_SNAKE_CASE       )

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






     def 							_lowercase      (					self       )				->     None:
          _snake_case				= []
          _snake_case				= 0

          _snake_case				= [-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       )

          _snake_case				= self.m_num_of_nodes

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

                    _snake_case				= self.m_component[u]
                    _snake_case				= 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
                              ):
                                   _snake_case				= [u, v, w]

               for edge in minimum_weight_edge:
                    if isinstance(_SCREAMING_SNAKE_CASE   ,_SCREAMING_SNAKE_CASE       ):
                         _snake_case				,   _snake_case				,   _snake_case				= edge

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

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

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







def       __a      (  )		->					None:

     """simple docstring"""






if __name__ == "__main__":
   import doctest

   doctest.testmod()


