


'''simple docstring'''

from __future__ import annotations

from typing import Any

class 		snake_case				:

				"""simple docstring"""




				def __init__(	self       ,    lowerCamelCase )    ->      None:







					"""simple docstring"""






					snake_case__			:			Any             =		num_of_nodes
					snake_case__			:			Union[str, Any]             =		[]
					snake_case__			:			List[Any]             =		{}





				def    lowercase__							(	self       ,    lowerCamelCase       ,    lowerCamelCase       ,    lowerCamelCase )    ->      None:







					"""simple docstring"""






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





				def    lowercase__							(	self       ,    lowerCamelCase )    ->      int:







					"""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       ,    lowerCamelCase )    ->      None:







					"""simple docstring"""






					if self.m_component[u_node] != u_node:
						for k in self.m_component:
							snake_case__			:			int             =		self.find_component(lowerCamelCase )





				def    lowercase__							(	self       ,    lowerCamelCase       ,    lowerCamelCase       ,    lowerCamelCase )    ->      None:







					"""simple docstring"""






					if component_size[u_node] <= component_size[v_node]:
						snake_case__			:			Union[str, Any]             =		v_node
						component_size[v_node] += component_size[u_node]
						self.set_component(lowerCamelCase )

					elif component_size[u_node] >= component_size[v_node]:
						snake_case__			:			str             =		self.find_component(lowerCamelCase )
						component_size[u_node] += component_size[v_node]
						self.set_component(lowerCamelCase )





				def    lowercase__							(	self )    ->      None:







					"""simple docstring"""






					snake_case__			:			Optional[int]             =		[]
					snake_case__			:			Optional[int]             =		0

					snake_case__			:			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 )

					snake_case__			:			List[Any]             =		self.m_num_of_nodes

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

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

						for edge in minimum_weight_edge:
							if isinstance(lowerCamelCase       ,    lowerCamelCase ):
								snake_case__      ,snake_case__      ,snake_case__			:			str             =		edge

								snake_case__			:			int             =		self.m_component[u]
								snake_case__			:			int             =		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

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






def 					_A			(			):
	pass





if __name__ == "__main__":
		import doctest

		doctest.testmod()










'''simple docstring'''





from __future__ import annotations




def lowerCAmelCase    (__A    ,      __A):



     """simple docstring"""



     if len(__A) == 0:
          return False
     _a           =    len(__A) // 2
     if a_list[midpoint] == item:
          return True
     if item < a_list[midpoint]:
          return binary_search(a_list[:midpoint]    ,      __A)
     else:
          return binary_search(a_list[midpoint + 1 :]    ,      __A)


if __name__ == "__main__":
  lowercase_									=    input("Enter numbers separated by comma:\n").strip()
  lowercase_									=    [int(item.strip()) for item in user_input.split(",")]
  lowercase_									=    int(input("Enter the number to be found in the list:\n").strip())
  lowercase_									=    "" if binary_search(sequence, target) else "not "
  print(F"""{target} was {not_str}found in {sequence}""")



