






'''simple docstring'''
from __future__ import annotations

import typing
from collections.abc import Iterable

import numpy as np

UpperCamelCase__ =			typing.Union[Iterable[float], Iterable[int], np.ndarray]  # noqa: UP007
UpperCamelCase__ =			typing.Union[np.floataa, int, float]  # noqa: UP007




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   return np.sqrt(np.sum((np.asarray(_UpperCamelCase							) - np.asarray(_UpperCamelCase							)) ** 2							)							)




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase						,		_UpperCamelCase							):


   """simple docstring"""




   return sum((va - va) ** 2 for va, va in zip(_UpperCamelCase						,		_UpperCamelCase							)							) ** (1 / 2)


if __name__ == "__main__":




 def 		__SCREAMING_SNAKE_CASE					(  ):


    """simple docstring"""




    from timeit import timeit

    print("Without Numpy"							)
    print(
        timeit(
            "euclidean_distance_no_np([1, 2, 3], [4, 5, 6])"						,		number=1_0000						,		globals=globals()						,		)							)
    print("With Numpy"							)
    print(
        timeit(
            "euclidean_distance([1, 2, 3], [4, 5, 6])"						,		number=1_0000						,		globals=globals()						,		)							)





 benchmark()












'''simple docstring'''
import heapq




def 		__SCREAMING_SNAKE_CASE					(  _UpperCamelCase							):


   """simple docstring"""




   lowercase_	:    list[list]           =     []

   # for each node and his adjacency list add them and the rank of the node to queue
   # using heapq module the queue will be filled like a Priority Queue
   # heapq works with a min priority queue, so I used -1*len(v) to build it
   for key, value in graph.items():
      # O(log(n))
      heapq.heappush(_UpperCamelCase						,		[-1 * len(_UpperCamelCase							), (key, value)]							)

   # chosen_vertices = set of chosen vertices
   lowercase_	:    Optional[Any]           =     set()

   # while queue isn't empty and there are still edges
   #   (queue[0][0] is the rank of the node with max rank)
   while queue and queue[0][0] != 0:
      # extract vertex with max rank from queue and add it to chosen_vertices
      lowercase_	:    Any           =     heapq.heappop(_UpperCamelCase							)[1][0]
      chosen_vertices.add(_UpperCamelCase							)

      # Remove all arcs adjacent to argmax
      for elem in queue:
         # if v haven't adjacent node, skip
         if elem[0] == 0:
            continue
         # if argmax is reachable from elem
         # remove argmax from elem's adjacent list and update his rank
         if argmax in elem[1][1]:
            lowercase_	:    str           =     elem[1][1].index(_UpperCamelCase							)
            del elem[1][1][index]
            elem[0] += 1
        # re-order the queue
      heapq.heapify(_UpperCamelCase							)
   return chosen_vertices


if __name__ == "__main__":
 import doctest

 doctest.testmod()

 UpperCamelCase__ =			{0: [1, 3], 1: [0, 3], 2: [0, 3, 4], 3: [0, 1, 2], 4: [2, 3]}
 print(f"""Minimum vertex cover:\n{greedy_min_vertex_cover(graph)}""")




