





_A					:    str   =  {0: [2, 3], 1: [0], 2: [1], 3: [4], 4: []}

_A					:    Tuple   =  {0: [1, 2, 3], 1: [2], 2: [0], 3: [4], 4: [5], 5: [3]}



def        _a						(    UpperCAmelCase			,  UpperCAmelCase			,  UpperCAmelCase     )				->				list[int]:







   """simple docstring"""
   lowerCamelCase__   :						Tuple					   =							True
   lowerCamelCase__   :						Optional[int]					   =							[]

   for neighbour in graph[vert]:
      if not visited[neighbour]:
         order += topology_sort(__snake_case			,  __snake_case			,  __snake_case     )

   order.append(__snake_case     )

   return order



def        _a						(    UpperCAmelCase			,  UpperCAmelCase			,  UpperCAmelCase     )				->				list[int]:







   """simple docstring"""
   lowerCamelCase__   :						Optional[int]					   =							True
   lowerCamelCase__   :						Optional[int]					   =							[vert]

   for neighbour in reversed_graph[vert]:
      if not visited[neighbour]:
         component += find_components(__snake_case			,  __snake_case			,  __snake_case     )

   return component




def        _a						(    UpperCAmelCase     )				->				list[list[int]]:







   """simple docstring"""
   lowerCamelCase__   :						Tuple					   =							len(__snake_case     ) * [False]
   lowerCamelCase__   :						Tuple					   =							{vert: [] for vert in range(len(__snake_case     )     )}

   for vert, neighbours in graph.items():
      for neighbour in neighbours:
         reversed_graph[neighbour].append(__snake_case     )

   lowerCamelCase__   :						Dict					   =							[]
   for i, was_visited in enumerate(__snake_case     ):
      if not was_visited:
         order += topology_sort(__snake_case			,  __snake_case			,  __snake_case     )

   lowerCamelCase__   :						Any					   =							[]
   lowerCamelCase__   :						Optional[int]					   =							len(__snake_case     ) * [False]

   for i in range(len(__snake_case     )     ):
      lowerCamelCase__   :						Dict					   =							order[len(__snake_case     ) - i - 1]
      if not visited[vert]:
         lowerCamelCase__   :						Union[str, Any]					   =							find_components(__snake_case			,  __snake_case			,  __snake_case     )
         components_list.append(__snake_case     )

   return components_list







from typing import Any
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						)     ->			list:







 """simple docstring"""


 _validation(
     __snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						)
 # Creates data structures and fill initial step
 _lowercase							      ={}
 _lowercase							      ={}
 for state in states_space:
  _lowercase							      =observations_space[0]
  _lowercase							      =(
      initial_probabilities[state] * emission_probabilities[state][observation]
  )
  _lowercase							      =None

 # Fills the data structure with the probabilities of
 # different transitions and pointers to previous states
 for o in range(1     ,						len(__snake_case						)						):
  _lowercase							      =observations_space[o]
  _lowercase							      =observations_space[o - 1]
  for state in states_space:
   # Calculates the argmax for probability function
   _lowercase							      =''''''
   _lowercase							      =-1
   for k_state in states_space:
    _lowercase							      =(
        probabilities[(k_state, prior_observation)]
        * transition_probabilities[k_state][state]
        * emission_probabilities[state][observation]
    )
    if probability > max_probability:
     _lowercase							      =probability
     _lowercase							      =k_state

            # Update probabilities and pointers dicts
   _lowercase							      =(
       probabilities[(arg_max, prior_observation)]
       * transition_probabilities[arg_max][state]
       * emission_probabilities[state][observation]
   )

   _lowercase							      =arg_max

    # The final observation
 _lowercase							      =observations_space[len(__snake_case						) - 1]

 # argmax for given final observation
 _lowercase							      =''''''
 _lowercase							      =-1
 for k_state in states_space:
  _lowercase							      =probabilities[(k_state, final_observation)]
  if probability > max_probability:
   _lowercase							      =probability
   _lowercase							      =k_state
 _lowercase							      =arg_max

 # Process pointers backwards
 _lowercase							      =last_state
 _lowercase							      =[]
 for o in range(len(__snake_case						) - 1     ,						-1     ,						-1						):
  result.append(__snake_case						)
  _lowercase							      =pointers[previous, observations_space[o]]
 result.reverse()

 return result
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						)     ->			None:







 """simple docstring"""


 _validate_not_empty(
     __snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						)
 _validate_lists(__snake_case     ,						__snake_case						)
 _validate_dicts(
     __snake_case     ,						__snake_case     ,						__snake_case						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case     ,						)     ->			None:







 """simple docstring"""


 if not all(
     [
         observations_space,
         states_space,
         initial_probabilities,
         transition_probabilities,
         emission_probabilities,
     ]						):
  raise ValueError('''There\'s an empty parameter'''						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case						)     ->			None:







 """simple docstring"""


 _validate_list(__snake_case     ,						'''observations_space'''						)
 _validate_list(__snake_case     ,						'''states_space'''						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case						)     ->			None:







 """simple docstring"""


 if not isinstance(_object     ,						__snake_case						):
  _lowercase							      =F"{var_name} must be a list"
  raise ValueError(__snake_case						)
 else:
  for x in _object:
   if not isinstance(__snake_case     ,						__snake_case						):
    _lowercase							      =F"{var_name} must be a list of strings"
    raise ValueError(__snake_case						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case     ,						__snake_case     ,						)     ->			None:







 """simple docstring"""


 _validate_dict(__snake_case     ,						'''initial_probabilities'''     ,						__snake_case						)
 _validate_nested_dict(__snake_case     ,						'''transition_probabilities'''						)
 _validate_nested_dict(__snake_case     ,						'''emission_probabilities'''						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case						)     ->			None:







 """simple docstring"""


 _validate_dict(_object     ,						__snake_case     ,						__snake_case						)
 for x in _object.values():
  _validate_dict(__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case						)
def 				UpperCAmelCase_					(							__snake_case     ,						__snake_case     ,						__snake_case     ,						__snake_case = False						)     ->			None:







 """simple docstring"""


 if not isinstance(_object     ,						__snake_case						):
  _lowercase							      =F"{var_name} must be a dict"
  raise ValueError(__snake_case						)
 if not all(isinstance(__snake_case     ,						__snake_case						) for x in _object						):
  _lowercase							      =F"{var_name} all keys must be strings"
  raise ValueError(__snake_case						)
 if not all(isinstance(__snake_case     ,						__snake_case						) for x in _object.values()						):
  _lowercase							      ='''nested dictionary ''' if nested else ''''''
  _lowercase							      =F"{var_name} {nested_text}all values must be {value_type.__name__}"
  raise ValueError(__snake_case						)


if __name__ == "__main__":
  from doctest import testmod

  testmod()

