Problem:


Bipartite Matching

A bipartite graph G = (V, E) is a graph in which the vertex set V can be divided into two disjoint subsets X and Y such that every edge e &isin; E has one end point in X and the other end point in Y.

A matching M is a subset of edges such that each node in V appears in at most one edge in M.

Given a bipartite graph, find the size of the matching which has the largest size.

Input

|X| |Y| |E|
x0 y0
x1 y1
:
x|E|-1 y|E|-1

|X| and |Y| are the number of vertices in X and Y respectively, and |E| is the number of edges in the graph G. The vertices in X are named with the numbers 0, 1,..., |X|-1, and vertices in Y are named with the numbers 0, 1,..., |Y|-1, respectively.

xi and yi are the node numbers from X and Y respectevely which represent the end-points of the i-th edge.

Output

Print the largest size of the matching.

Constraints

1 ≤ |X|, |Y| ≤ 100

0 ≤ |E| ≤ 10,000

Sample Input 1

3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

Sample Output 1

3



Sample input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3


Sample output:
3

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys
from collections import deque


def generate_adj_table(_edges):
    for edge in _edges:
        source, target = map(int, edge)
        target += x_num
        init_adj_table[source].append(target)
        init_adj_table[target].append(source)

    return init_adj_table


def graph_bfs_Hungarian():
    ans = 1
    queue = deque()
    prev, matching = ([-1] * v_num for _ in range(2))
    visited = [False] * v_num

    for v in range(x_num):
        if matching[v] == -1:
            while queue:
                queue.pop()
            queue.append(v)
            prev[v] = -1
            flag = False
            while queue and not flag:
                current = queue[0]
                for adj in adj_table[current]:
                    if not visited[adj]:
                        visited[adj] = True
                        queue.append(matching[adj])
                        if matching[adj] >= 0:
                            prev[matching[adj]] = current
                        else:
                            flag = True
                            # print(current, adj)
                            d, e = current, adj
                            while d != -1:
                                t = matching[d]
                                matching[d] = e
                                matching[e] = d
                                d = prev[d]
                                e = t

                queue.pop()

            if matching[v] != -1:
                ans += 1

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(v_num)]
    adj_table = generate_adj_table(edges)
    print(graph_bfs_Hungarian())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys
# from collections import deque


def generate_adj_table(_edges):
    for edge in _edges:
        source, target = map(int, edge)
        target += x_num
        init_adj_table[source].append(target)
        init_adj_table[target].append(source)

    return init_adj_table


def graph_bfs_Hungarian():
    ans = 0
    queue = list()
    prev, matching = ([-1] * v_num for _ in range(2))
    visited = [False] * v_num

    for v in range(x_num):
        if matching[v] == -1:
            while queue:
                queue.pop()
            queue.append(v)
            prev[v] = -1
            flag = False
            while queue and not flag:
                current = queue[0]
                for adj in adj_table[current]:
                    if not flag:
                        if not visited[adj]:
                            visited[adj] = True
                            queue.append(matching[adj])
                            if matching[adj] >= 0:
                                prev[matching[adj]] = current
                            else:
                                flag = True
                                # print(current, adj)
                                d, e = current, adj
                                while d != -1:
                                    t = matching[d]
                                    matching[d] = e
                                    matching[e] = d
                                    d = prev[d]
                                    e = t

                queue.pop()

            if matching[v] != -1:
                ans += 1

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(v_num)]
    adj_table = generate_adj_table(edges)
    print(graph_bfs_Hungarian())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        init_adj_table[vx].append(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if adj in adj_table[current] and not visited[adj]:
            visited[adj] = True
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * y_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    print(matching)
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        init_adj_table[vx].add(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if not visited[adj]:
            visited[adj] = True
            # matching[adj] = -1: adj not assigned to any of x
            # graph_dfs(matching[adj], matching, visited) = True
            # indicates that source in x has been already assigned to another target in y
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * y_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    # print(matching)
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    init_adj_table = [set() for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())

Submission status: Wrong Answer

Solution code:
# Acceptance of input

import sys

file_input = sys.stdin

X, Y, E = map(int, file_input.readline().split())

v_num = X + Y + 2

adj_mat = [[0] * (v_num) for i in range(v_num)]

for line in file_input:
    x, y = map(int, line.split())
    adj_mat[x][X + y] = 1

s = X + Y
t = s + 1

for i in range(X):
    adj_mat[s][i] = 1

for i in range(X, s):
    adj_mat[i][t] = 1

# Dinic's algorithm

import collections

# BFS for residual capacity network to construct level graph
def bfs(start, goal, parent):
    unvisited = [True] * v_num
    queue = collections.deque()
    queue.append(start)
    unvisited[start] = False
    while queue:
        u = queue.popleft()
        for v, r_capacity in enumerate(adj_mat[u]):
            if unvisited[v] and (r_capacity > 0):
                parent[v].append(u)
                queue.append(v)
                unvisited[v] = False
    return unvisited[goal]

# DFS for level graph and construct blocking flow
def dfs(goal, path, parent, blocking_flow):
    v = path[-1]
    if v == goal:
        aug_path_flow = 10000
        for x, y in zip(path[1:], path[:-1]):
            aug_path_flow = min(aug_path_flow, adj_mat[x][y])
        for x, y in zip(path[1:], path[:-1]):
            adj_mat[x][y] -= aug_path_flow
            adj_mat[y][x] += aug_path_flow
        blocking_flow[0] += aug_path_flow
    else:
        for u in parent[v]:
            path.append(u)
            dfs(goal, path, parent, blocking_flow)
            path.pop()

def dinic(source, sink):
    max_flow = 0
    parent = [[] for i in range(v_num)]
    while not bfs(source, sink, parent):
        blocking_flow = [0]
        path = [sink]
        # search in reverse direction from sink
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(v_num)]
    return max_flow

# output
print(dinic(0, v_num - 1))

Submission status: Wrong Answer

Solution code:
def dfs(u):
    for v in range(nv):
        if adj[u][v] and not visited[v]:
            visited[v] = True
            if not matches[v] or dfs(matches[v]):
                matches[v] = u
                return True
    return False

nu, nv, ne = map(int, input().split(' '))
adj = [[False] * nv for _ in range(nu)]
matches = [None] * nv
count = 0

for _ in range(ne):
    s, t = map(int, input().split(' '))
    adj[s][t] = True

for i in range(nu):
    visited = [False] * ne
    if dfs(i): count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def dfs(s):
    if s in settled:
        return False
    stack = [s]
    visited = set()
    is_y = False
    while stack:
        vertex = stack.pop()
        if is_y and vertex not in settled:
            settled.add(s)
            settled.add(vertex)
            return True
        if vertex in visited:
            continue
        visited.add(vertex)
        stack.extend(edges[vertex] - visited)
        is_y = not is_y
    return False


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn + yn)]
settled = set()

for _ in range(e):
    x, y = map(int, input().split())
    y += xn
    edges[x].add(y)
    edges[y].add(x)

print(sum(map(dfs, range(xn))))

Submission status: Wrong Answer

Solution code:
def dfs(s):
    stack = [(s, -1)]
    visited = set()
    while stack:
        v, prev = stack.pop()
        if v < xn:
            if matched[v] == -1:
                matched[v] = prev
                return True
            if v in visited:
                continue
            visited.add(v)
            stack.append((matched[v], v))
            matched[v] = prev
        else:
            stack.extend((w, v) for w in (edges[v] - visited))
    return False


xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn + yn)]
matched = [-1] * xn

for _ in range(e):
    x, y = map(int, input().split())
    y += xn
    edges[x].add(y)
    edges[y].add(x)

print(sum(map(dfs, range(xn, xn + yn))))

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def dfs(here):
    used[here] = 1
    for near in connect[here]:
        if not match[near] or (not used[near] and dfs(near)):
            match[here] = near
            match[near] = here
            return 1
        return 0
    
a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [0 for n in range(all_v)]
used = [0 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num + 1
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = 0
for i in range(all_v):
    if not match[i] and dfs(i):
        answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [0 for n in range(all_v)]
used = [0 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num + 1
    connect[v1].append(v2)
    connect[v2].append(v1)
def dfs(here,used,match,connect):
    used[here] = 1
    for near in connect[here]:
        if not match[near] or (not used[near] and dfs(near,used,match,connect)):
            match[here] = near
            match[near] = here
            return 1
    return 0


answer = 0
for i in range(all_v):
    if not match[i] and dfs(i,used,match,connect):
        answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [0 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num + 1
    connect[v1].append(v2)
    connect[v2].append(v1)
def dfs(here,used,match,connect):
    used[here] = 1
    for near in connect[here]:
        m = match[near]
        if m < 0 or (not used[m] and dfs(m,used,match,connect)):
            match[here] = near
            match[near] = here
            return 1
    return 0

answer = 0
for i in range(all_v):
    if match[i] < 0:
        if dfs(i,used,match,connect):
            used = [0 for n in range(all_v)]
            answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def dfs(here,used,match,connect):
    used[here] = 1
    for near in connect[here]:
        m = match[near]
        if m < 0 or (not used[m] and dfs(m,used,match,connect)):
            match[here] = near
            match[near] = here
            return 1
        return 0
    
a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [0 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = 0
for i in range(all_v):
    if match[i] < 0:
        if dfs(i,used,match,connect):
            used = [0 for n in range(all_v)]
            answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
def dfs(here,used,match,connect):
    used[here] = 1
    for near in connect[here]:
        m = match[near]
        if m < 0 or (not used[m] and dfs(m,used,match,connect)):
            match[here] = near
            match[near] = here
            return 1
    return 0

a_num, b_num, e_num = (int(n) for n in input().split(" "))
connect = defaultdict(list)
all_v = a_num + b_num
match = [0 for n in range(all_v)]
for _ in range(e_num):
    v1, v2 = (int(n) for n in input().split(" "))
    v2 += a_num
    connect[v1].append(v2)
    connect[v2].append(v1)
answer = 0
for i in range(all_v):
    if match[i] < 0:
        if dfs(i,used,match,connect):
            used = [0 for n in range(all_v)]
            answer += 1
print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Matching - Bipartite Matching
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_7_A&lang=jp

"""
import sys
from sys import stdin
from collections import namedtuple
input = stdin.readline
edge = namedtuple('edge', ['to', 'cap', 'rev'])


def add_edge(G, f, t, c):
    G[f].append(edge(t, c, len(G[t])))
    G[t].append(edge(f, 0, len(G[f]) - 1))


def dfs(G, used, v, t, f):
    if v == t:
        return f
    used[v] = True
    for i in range(len(G[v])):
        e = G[v][i]
        if (not used[e.to]) and (e.cap > 0):
            d = dfs(G, used, e.to, t, min(f, e.cap))
            if d > 0:
                G[v][i] = edge(e.to, e.cap - d, e.rev)
                G[e.to][e.rev] = edge(G[e.to][e.rev].to, G[e.to][e.rev].cap + d, G[e.to][e.rev].rev)
                return d
    return 0


def max_flow(G, V, s, t):
    used = [False] * V
    flow = 0
    while True:
        for i in range(len(used)):
            used[i] = False
        f = dfs(G, used, s, t, float('inf'))
        if f == 0:
            return flow
        flow += f


def main(args):
    """
    - 追加したソースノードID: 0
    - Xグループ: 1〜X
    - Yグループ: X+1〜X+Y
    - 追加したシンクノードID: X+Y+1
    として、ノード0 → X+Y+1 への最大流を求める
    """
    X, Y, E = map(int, input().split())
    G = [[] for _ in range(X+Y+2)]

    for li in range(E):
        x, y = map(int, input().split())
        add_edge(G, 0, x, 1)
        add_edge(G, y, X+Y+1, 1)
        add_edge(G, x+1, X+y+1, 1)

    ans = max_flow(G, X+Y+2, 0, X+Y+1) #  ソースとシンク間の最大流
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys
from collections import deque


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        # vy += x_num
        init_adj_table[vx].append(vy)
        # init_adj_table[vy].append(vx)

    return init_adj_table


def graph_bfs_Hungarian():
    ans = 0
    queue = list()
    prev = [-1] * y_num
    matching = [-1] * y_num

    for v in range(x_num):
        visited = [False] * y_num
        if matching[v] == -1:
            while queue:
                queue.pop()
            queue.append(v)
            prev[v] = -1
            flag = False
            while queue and not flag:
                current = queue[0]
                for adj in adj_table[current]:
                    if not flag:
                        if not visited[adj]:
                            visited[adj] = True
                            queue.append(matching[adj])
                            if matching[adj] >= 0:
                                prev[matching[adj]] = current
                            else:
                                flag = True
                                d, e = current, adj
                                while d != -1:
                                    t = matching[d]
                                    matching[d] = e
                                    # matching[e] = d
                                    d = prev[d]
                                    e = t

                queue.pop()

            if matching[v] != -1:
                ans += 1

    return ans


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    # v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(graph_bfs_Hungarian())

Submission status: Accepted

Solution code:
import sys
from collections import deque


class MaxFlow:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, node_size, inf):
        self._node = node_size
        self._inf = inf
        self._level = [-1]*self._node
        self._iter = [0]*self._node
        self._graph = [[] for _ in range(self._node)]

    def add_edge(self, from_, to, cap):
        self._graph[from_].append(self.Edge(to, cap, len(self._graph[to])))
        self._graph[to].append(self.Edge(from_, 0, len(self._graph[from_])-1))

    def bfs(self, start):
        self._level = [-1]*self._node
        que = deque()
        self._level[start] = 0
        que.append(start)
        while que:
            cur_vertex = que.popleft()
            for e in self._graph[cur_vertex]:
                if self._level[e.to] < 0 < e.cap:
                    self._level[e.to] = self._level[cur_vertex] + 1
                    que.append(e.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:
            return flow
        for e in self._graph[cur_vertex][self._iter[cur_vertex]:len(self._graph[cur_vertex])]:
            if e.cap > 0 and self._level[cur_vertex] < self._level[e.to]:
                flowed = self.dfs(e.to, end_vertex, min(flow, e.cap))
                if flowed > 0:
                    e.cap -= flowed
                    self._graph[e.to][e.rev].cap += flowed
                    return flowed
        return 0

    def solve(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self._level[sink] < 0:
                return flow
            self._iter = [0]*self._node
            while True:
                f = self.dfs(source, sink, self._inf)
                if f == 0:
                    break
                flow += f


class BipartiteMatching:
    def __init__(self, size1, size2):
        self._u_size, self. _v_size = size1, size2
        self.mf = MaxFlow(self._u_size+self. _v_size+2, min(self._u_size, self._v_size))
        for i in range(self._u_size):
            self.mf.add_edge(0, i+1, 1)
        for i in range(self._v_size):
            self.mf.add_edge(self._u_size+i+1, self._u_size+self._v_size+1, 1)

    def add_edge(self, from_, to):
        self.mf.add_edge(from_+1, to+self._u_size+1, 1)

    def solve(self):
        return self.mf.solve(0, self._u_size+self._v_size+1)

if __name__=='__main__':
    x, y, m = map(int, sys.stdin.readline().split())
    bm = BipartiteMatching(x, y)
    for _ in range(m):
        u, v = map(int, sys.stdin.readline().split())
        bm.add_edge(u, v)
    print(bm.solve())

Submission status: Accepted

Solution code:
from sys import stdin
from collections import defaultdict
readline = stdin.readline



def main():
    x, y, e = map(int, readline().split())
    g = defaultdict(list)
    residual = [[0] * (x + y + 2) for _ in range(x + y + 2)]
    source, sink = x + y, x + y + 1
    # source->x
    for xi in range(x):
        g[source].append(xi)
        residual[source][xi] = 1
    # y->sink
    for yi in range(x, x + y):
        g[yi].append(sink)
        residual[yi][sink] = 1
    # x <-> y
    for _ in range(e):
        s, t = map(int, readline().split())
        t += x
        g[s].append(t)
        g[t].append(s)
        residual[s][t] = 1

    while True:
        route, flow = search(g, residual, source, sink)
        if not route:
            break
        for s, t in zip(route, route[1:]):
            residual[s][t] -= flow
            residual[t][s] += flow
    print(sum(residual[sink]))


def search(g, residual, source, sink):
    dfs_stack = [(source, None, float('inf'))]
    route = [None]
    visited = set()
    while dfs_stack:
        u, prev, flow = dfs_stack.pop()
        while route[-1] != prev:
            route.pop()
        route.append(u)
        visited |= {u}
        if u == sink:
            return route[1:], flow
        for v in g[u]:
            if v not in visited and 0 < residual[u][v]:
                dfs_stack.append((v, u, min(residual[u][v], flow)))
    return [], 0
main()

Submission status: Accepted

Solution code:
def read_data():
    X, Y, E = map(int, input().split())
    Ss = list(range(X))
    Ts = list(range(X, X + Y))
    Es = []
    for i in range(E):
        x, y = map(int, input().split())
        Es.append((x, y + X))
    return Ss, Ts, Es
    

def bp_match(Ss, Ts, Es):
    '''2??¨??°???????????????????????°???????????¨??????
    '''
    super_source = len(Ss) + len(Ts)
    super_target = super_source + 1
    Cs = [dict() for i in range(super_target + 1)]
    for si, ti in Es:
        Cs[si][ti] = 1
        Cs[ti][si] = 0
    for si in Ss:
        Cs[super_source][si] = 1
        Cs[si][super_source] = 0
    for ti in Ts:
        Cs[super_target][ti] = 0
        Cs[ti][super_target] = 1
    return dinic(Cs, super_target + 1, super_source, super_target)

def dinic(cf, nV, s, t):
    dist = get_distance(cf, s, t)
    while dist[t] > 0:
        df = dfs(dist, cf, s, t, float('inf'))
        while df:
            df = dfs(dist, cf, s, t, float('inf'))
        dist = get_distance(cf, s, t)
    return sum(cf[t].values())

def get_distance(cf, s, t):
    dist = [-1] * len(cf)
    dist[s] = 0
    frontiers = [s]
    while frontiers:
        new_frontiers = []
        for u in frontiers:
            for v, capacity in cf[u].items():
                if dist[v] == -1 and capacity > 0:
                    dist[v] = dist[u] + 1
                    new_frontiers.append(v)
        frontiers = new_frontiers
    return dist

def dfs(dist, cf, u, t, df):
    if u == t:
        return df
    for v, capacity in cf[u].items():
        if dist[v] > dist[u] and capacity > 0:
            new_df = dfs(dist, cf, v, t, min(df, capacity))
            if new_df > 0:
                cf[u][v] -= new_df
                cf[v][u] += new_df
                return new_df
    return 0

if __name__ == '__main__':
#    Ss = [0, 1, 2, 3, 4]
#    Ts = [5, 6, 7, 8]
#    Es = [(0, 5), (1, 5), (1, 7), (2, 6), (2, 7), (2, 8), (3, 7), (4, 7)]
    Ss, Ts, Es = read_data()
    print(bp_match(Ss, Ts, Es))

Submission status: Accepted

Solution code:
class BipartiteGraph(object):
    
    def __init__(self, num_nodes):
        self.graph = [[] for _ in range(num_nodes)] # ??°???????????£??\???????????¨???
        self.match = [None] * num_nodes # ??????????????°????????¢

    def add_edge(self, u, v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def has_increasing_path(self, v, used):
        used[v] = True
        for i, u in enumerate(self.graph[v]):
            w = self.match[u]
            if w is None or (not used[w] and self.has_increasing_path(w, used)):
                self.match[v] = u
                self.match[u] = v
                return True
        return False

    def __str__(self):
        ret = ["graph bipartite_graph {"]
        for v, g in enumerate(self.graph):
            for u in g:
                ret.append("    {} -- {};".format(v, u))
        # ret.append("    rank = source; {};"
        ret.append("}")
        return "\n".join(ret)
        

    def solve(self):
        ret = 0
        for v in range(len(self.graph)):
            if self.match[v] is not None:
                continue
            if self.has_increasing_path(v, [False]*len(self.graph)):
                ret += 1
        return ret

if __name__ == "__main__":
    X, Y, E = list(map(int, input().split()))
    bg = BipartiteGraph(X+Y)
    for _ in range(E):
        x, y = list(map(int, input().split()))
        y += X
        bg.add_edge(x, y)
    print(bg.solve())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        # vy += x_num
        init_adj_table[vx].append(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if adj in adj_table[current] and not visited[adj]:
            visited[adj] = True
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * v_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        init_adj_table[vx].append(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if adj in adj_table[current] and not visited[adj]:
            visited[adj] = True
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * v_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        init_adj_table[vx].append(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if adj in adj_table[current] and not visited[adj]:
            visited[adj] = True
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * y_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    # print(matching)
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
input:
3 4 6
0 0
0 2
0 3
1 1
2 1
2 3

output:
3
"""

import sys


def generate_adj_table(_edges):
    for edge in _edges:
        vx, vy = map(int, edge)
        init_adj_table[vx].append(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if adj in adj_table[current] and not visited[adj]:
            visited[adj] = True
            if matching[adj] == -1 or graph_dfs(matching[adj], matching, visited):
                matching[adj] = current
                return True
    return False


def mbm():
    matching = [-1] * y_num
    res = 0
    for v in range(x_num):
        visited = [False] * y_num
        if graph_dfs(v, matching, visited):
            res += 1
    # print(matching)
    return res


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    x_num, y_num, e_num = map(int, _input[0].split())
    edges = map(lambda x: x.split(), _input[1:])

    # v_num = x_num + y_num
    init_adj_table = [[] for _ in range(x_num)]
    adj_table = generate_adj_table(edges)
    print(mbm())