# Path: tryalgo/bipartite_matching.py
# def max_bipartite_matching(bigraph):
#     """Bipartie maximum matching
# 
#     :param bigraph: adjacency list, index = vertex in U,
#                                     value = neighbor list in V
#     :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
#     :returns: matching list, match[v] == u iff (u, v) in matching
#     :complexity: `O(|V|*|E|)`
#     """
#     n = len(bigraph)               # same domain for U and V
#     match = [None] * n
#     for u in range(n):
#         augment(u, bigraph, [False] * n, match)
#     return match


from tryalgo.bipartite_matching import max_bipartite_matching
"""




def _alternate(u, bigraph, visitU, visitV, matchV):
    """extend alternating tree from free vertex u.
      visitU, visitV marks all vertices covered by the tree.
    """
    visitU[u] = True
    for v in bigraph[u]:
        if not visitV[v]:
            visitV[v] = True
            assert matchV[v] is not None  # otherwise match is not maximum
            _alternate(matchV[v], bigraph, visitU, visitV, matchV)


def bipartite_vertex_cover(bigraph):
    """Bipartite minimum vertex cover by Koenig's theorem

    :param bigraph: adjacency list, index = vertex in U,
                                    value = neighbor list in V
    :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
    :returns: boolean table for U, boolean table for V
    :comment: selected vertices form a minimum vertex cover,
              i.e. every edge is adjacent to at least one selected vertex
              and number of selected vertices is minimum
    :complexity: `O(|V|*|E|)`
    """
    V = range(len(bigraph))

# Path: tryalgo/bipartite_matching.py
# def max_bipartite_matching(bigraph):
#     """Bipartie maximum matching
# 
#     :param bigraph: adjacency list, index = vertex in U,
#                                     value = neighbor list in V
#     :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
#     :returns: matching list, match[v] == u iff (u, v) in matching
#     :complexity: `O(|V|*|E|)`
#     """
#     n = len(bigraph)               # same domain for U and V
#     match = [None] * n
#     for u in range(n):
#         augment(u, bigraph, [False] * n, match)
#     return match


# Path: tryalgo/bipartite_vertex_cover.py
from tryalgo.bipartite_matching import max_bipartite_matching

"""




def _alternate(u, bigraph, visitU, visitV, matchV):
    """extend alternating tree from free vertex u.
      visitU, visitV marks all vertices covered by the tree.
    """
    visitU[u] = True
    for v in bigraph[u]:
        if not visitV[v]:
            visitV[v] = True
            assert matchV[v] is not None  # otherwise match is not maximum
            _alternate(matchV[v], bigraph, visitU, visitV, matchV)


def bipartite_vertex_cover(bigraph):
    """Bipartite minimum vertex cover by Koenig's theorem

    :param bigraph: adjacency list, index = vertex in U,
                                    value = neighbor list in V
    :assumption: U = V = {0, 1, 2, ..., n - 1} for n = len(bigraph)
    :returns: boolean table for U, boolean table for V
    :comment: selected vertices form a minimum vertex cover,
              i.e. every edge is adjacent to at least one selected vertex
              and number of selected vertices is minimum
    :complexity: `O(|V|*|E|)`
    """
    V = range(len(bigraph))

    matchV = max_bipartite_matching(bigraph)