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: 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 (not visited[adj]) and adj in adj_table[current]:
            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:])

    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 (not visited[adj]) and (adj in adj_table[current]):
            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:])

    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].add(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if (not visited[adj]) and (adj in adj_table[current]):
            visited[adj] = True
            # matching[adj] = -1: target in y not assigned to any of x
            # matching[adj] -> an assigned source in x
            # graph_dfs(matching[adj], matching, visited) = True indicates that source has been
            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: 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].add(vy)

    return init_adj_table


def graph_dfs(current, matching, visited):
    for adj in range(y_num):
        if (not visited[adj]) and (adj in adj_table[current]):
            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: 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].add(vy)

    return init_adj_table


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


def mbm():
    matching = [-1] * y_num
    res = 0
    for source in range(x_num):
        visited = [False] * y_num
        if graph_dfs(source, 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: 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 graph_dfs(current, matching, visited):
    for target in range(y_num):
        if (not visited[target]) and (target in adj_table[current]):
            visited[target] = True
            if matching[target] == -1 or graph_dfs(matching[target], matching,
                                                   visited):
                matching[target] = current
                return True
    return False


def mbm():
    res = 0
    matching = [-1] * y_num
    for source in range(x_num):
        visited = [False] * y_num
        if graph_dfs(source, 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:])

    adj_table = [set() for _ in range(x_num)]
    for edge in edges:
        vx, vy = map(int, edge)
        adj_table[vx].add(vy)
    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 dfs(current, matching, visited):
    for target in range(y_num):
        if not visited[target] and target in adj_table[current]:
            visited[target] = True
            ''' Matching[target] = -1: target not assigned to any of x.
            And dfs(matching[target], matching, visited) = True
            indicates that source in x has been already assigned
            to another target in y. '''
            if matching[target] == -1 or dfs(matching[target], matching, visited):
                matching[target] = current
                return True
    return False


def mbm():
    res = 0
    matching = [-1] * y_num
    for source in range(x_num):
        visited = [False] * y_num
        if dfs(source, 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:])

    adj_table = tuple([] for _ in range(x_num))
    for edge in edges:
        vx, vy = map(int, edge)
        adj_table[vx].append(vy)
    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 dfs(current, matching, visited):
    for target in range(y_num):
        if not visited[target] and target in adj_table[current]:
            visited[target] = True
            ''' Matching[target] = -1: target not assigned to any of x.
            And dfs(matching[target], matching, visited) = True
            indicates that source in x has been already assigned
            to another target in y. '''
            if matching[target] == -1 or dfs(matching[target], matching, visited):
                matching[target] = current
                return True
    return False


def mbm():
    res = 0
    matching = [-1] * y_num
    for source in range(x_num):
        visited = [False] * y_num
        if dfs(source, 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:])

    adj_table = tuple(set() for _ in range(x_num))
    for edge in edges:
        vx, vy = map(int, edge)
        adj_table[vx].add(vy)
    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 dfs(current, matching, visited):
    for target in range(y_num):
        if (not visited[target]) and (target in adj_table[current]):
            visited[target] = True
            ''' Matching[target] = -1: target not assigned to any of x.
            And dfs(matching[target], matching, visited) = True
            indicates that source in x has been already assigned
            to another target in y. '''
            if matching[target] == -1 or dfs(matching[target], matching, visited):
                matching[target] = current
                return True
    return False


def mbm():
    res = 0
    matching = [-1] * y_num
    for source in range(x_num):
        visited = [False] * y_num
        if dfs(source, 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:])

    adj_table = tuple(set() for _ in range(x_num))
    for edge in edges:
        vx, vy = map(int, edge)
        adj_table[vx].add(vy)
    print(mbm())

Submission status: Accepted

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

# Ford???Fulkerson method

import collections

# BFS for residual capacity network
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):
                queue.append(v)
                unvisited[v] = False
                parent[v] = u
                if v == goal:
                    return not unvisited[goal]

def ford_fulkerson(source, sink):
    parent = [None] * v_num
    max_flow = 0
    while bfs(source, sink, parent):
        aug_path_flow = 10000
        v = sink
        while (v != source):
            aug_path_flow = min(aug_path_flow, adj_mat[parent[v]][v])
            v = parent[v]
        max_flow += aug_path_flow
        v = sink
        while (v != source):
            u = parent[v]
            adj_mat[u][v] -= aug_path_flow
            adj_mat[v][u] += aug_path_flow
            v = u
    return max_flow

# output
print(ford_fulkerson(s, t))

Submission status: Accepted

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(s, t))

Submission status: Accepted

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):
    level = [v_num] * v_num
    unvisited = [True] * v_num
    queue = collections.deque()
    queue.append(start)
    level[start] = 0
    unvisited[start] = False
    while queue:
        u = queue.popleft()
        next_level = level[u] + 1
        for v, r_capacity in enumerate(adj_mat[u]):
            if (level[v] >= next_level) and (r_capacity > 0):
                level[v] = next_level
                parent[v].append(u)
                if unvisited[v]:
                    queue.append(v)
                    unvisited[v] = False
    return level[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 bfs(source, sink, parent) != v_num:
        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(s, t))

Submission status: Accepted

Solution code:
def dfs(u):
    for v in range(nv):
        if adj[u][v] and not visited[v]:
            visited[v] = True
            if matches[v] is None 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 u in range(nu):
    visited = [False] * nv
    if dfs(u): count += 1

print(count)

Submission status: Accepted

Solution code:
import sys
from queue import deque

sys.setrecursionlimit(200000)


def hierarchize(source):
    global hierarchy
    hierarchy = [-1] * n
    queue = deque([(0, source)])
    while queue:
        h, v = queue.popleft()
        if hierarchy[v] != -1:
            continue
        hierarchy[v] = h
        if v == sink:
            return True
        queue.extend((h + 1, target)
                     for remain, target, _ in edges[v] if hierarchy[target] == -1 and remain)
    return False


def augment(v, limit):
    if v == sink:
        return limit
    res = 0
    for e in edges[v]:
        remain, target, idx = e
        if remain == 0 or hierarchy[v] >= hierarchy[target]:
            continue
        aug = augment(target, min(limit, remain))
        e[0] -= aug
        edges[target][idx][0] += aug
        res += aug
        limit -= aug
        if not limit:
            break
    return res


xn, yn, e = map(int, input().split())
n = xn + yn + 2
sink = n - 1
edges = [[] for _ in range(n)]

hierarchy = [-1] * n

for x in range(xn):
    xi = x + 1
    edges[0].append([1, xi, 0])
    edges[xi].append([0, 0, x])
for y in range(yn):
    yi = xn + y + 1
    edges[yi].append([1, sink, y])
    edges[sink].append([0, yi, 0])

for _ in range(e):
    x, y = map(int, input().split())
    xi, yi = x + 1, xn + y + 1
    ex, ey = edges[xi], edges[yi]
    lx, ly = len(ex), len(ey)
    ex.append([1, yi, ly])
    ey.append([0, xi, lx])

res = 0
while hierarchize(0):
    res += augment(0, 100)
print(res)

Submission status: Accepted

Solution code:
def dfs(s):
    return _dfs(s, set())


def _dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or _dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


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

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

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

Submission status: Accepted

Solution code:
def dfs(v, edges, visited, matched):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], edges, visited, matched):
            matched[u] = v
            return True
    return False


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

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

print(sum(dfs(s, edges, set(), matched) for s in range(xn)))

Submission status: Accepted

Solution code:
def dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


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

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

print(sum(dfs(s, set()) for s in range(xn)))

Submission status: Accepted

Solution code:
def dfs(v, visited):
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


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

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

print(sum(map(lambda s: dfs(s, set()), range(xn))))

Submission status: Accepted

Solution code:
import collections
class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]
    def add_edge(self, fr, to, cap):
        self.g[fr].append([to, cap, len(self.g[to])])
        self.g[to].append([fr, 0, len(self.g[fr])-1])
    def add_multi_edge(self, v1, v2, cap1, cap2):
        self.g[v1].append([v2, cap1, len(self.g[v2])])
        self.g[v2].append([v1, cap2, len(self.g[v1])-1])
    def bfs(self, s):
        level = [-1]*self.n
        deq = collections.deque()
        level[s] = 0
        deq.append(s)
        while deq:
            v = deq.popleft()
            for e in self.g[v]:
                if e[1]>0 and level[e[0]]<0:
                    level[e[0]] = level[v] + 1
                    deq.append(e[0])
        self.level = level
    def dfs(self, v, t, f):
        if v==t: return f
        es = self.g[v]
        level = self.level
        for i in range(self.it[v], len(self.g[v])):
            e = es[i]
            if e[1]>0 and level[v]<level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d
                    self.g[e[0]][e[2]][1] += d
                    self.it[v] = i
                    return d
        self.it[v] = len(self.g[v])
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0: break
            self.it = [0]*self.n
            while True:
                f = self.dfs(s, t, 10**9+7)
                if f>0:
                    flow += f
                else:
                    break
        return flow

X, Y, E = map(int, input().split())
dinic = Dinic(2+X+Y)
for i in range(X):
    dinic.add_edge(0, 2+i, 1)
for i in range(Y):
    dinic.add_edge(2+X+i, 1, 1)
for i in range(E):
    x, y = map(int, input().split())
    dinic.add_edge(2+x, 2+X+y, 1)
print(dinic.max_flow(0, 1))

Submission status: Accepted

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 = [-1 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:
        used = [0 for n in range(all_v)]
        if dfs(i,used,match,connect):
            answer += 1
print(answer)

Submission status: Accepted

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):
    flow = 0
    while True:
        used = [False] * V
        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, x+1, X+y+1, 1)

    for x in range(1, X+1):
        add_edge(G, 0, x, 1)       # ソースから集合X
    for y in range(X+1, X+Y+1):
        add_edge(G, y, X+Y+1, 1)   # 集合Yからシンク


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


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

Submission status: Accepted

Solution code:
class BipartiteMatching:
    def __init__(self, V):
        self.V = V
        self.G = [[] for _ in range(V)]

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

    def dfs(self, u):
        self.used[u] = True
        for v in self.G[u]:
            w = self.match[v]
            if w < 0 or (not self.used[w] and self.dfs(w)):
                self.match[u] = v
                self.match[v] = u
                return True
        return False

    def bipartite_matching(self):
        res = 0
        self.match = [-1] * self.V
        for v in range(self.V):
            if self.match[v] == -1:
                self.used = [False] * self.V
                if self.dfs(v):
                    res += 1
        return res

X, Y, E = map(int, input().split())
bm = BipartiteMatching(X+Y)
for _ in range(E):
    x, y = map(int, input().split())
    bm.add_edge(x, X + y)
print(bm.bipartite_matching())

Submission status: Accepted

Solution code:
class Node():
    def __init__(self):
        self.edge = []
        self.level = None
        self.par = None
        self.cap = 10**18

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

from collections import deque

class BipartiteMatching():
    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.inf = 10**18
        self.source = Node()
        self.sink = Node()
        self.lt = [Node() for _ in range(n)]
        self.rt = [Node() for _ in range(m)]
        for i in range(n):
            edge = Edge(self.lt[i], 1)
            rev = Edge(self.source, 0)
            edge.rev, rev.rev = rev, edge
            self.source.edge.append(edge)
            self.lt[i].edge.append(rev)
        for i in range(m):
            edge = Edge(self.sink, 1)
            rev = Edge(self.rt[i], 0)
            edge.rev, rev.rev = rev, edge
            self.rt[i].edge.append(edge)
            self.sink.edge.append(rev)

    def add(self, x, y):
        lt = self.lt[x]
        rt = self.rt[y]
        edge = Edge(rt, 1)
        rev = Edge(lt, 0)
        edge.rev, rev.rev = rev, edge
        lt.edge.append(edge)
        rt.edge.append(rev)

    def maximum_matching(self):
        flow = 0
        while True:
            queue = deque([self.source])
            self.source.level = 0
            self.sink.level = None
            for i in range(self.n):
                self.lt[i].level = None
            for i in range(self.m):
                self.rt[i].level = None
            while queue:
                node = queue.popleft()
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and to.level is None:
                        to.level = node.level + 1
                        queue.append(to)
            if self.sink.level is None: break
            stack = [self.source]
            self.source.par = None
            self.sink.par = None
            for i in range(self.n):
                self.lt[i].par = None
            for i in range(self.m):
                self.rt[i].par = None
            while stack:
                node = stack.pop()
                if node is self.sink:
                    break
                for edge in node.edge:
                    to = edge.to
                    if edge.cap and node.level < to.level:
                        to.par = edge.rev
                        #to.cap = min(edge.cap, node.cap)
                        stack.append(to)
            node = self.sink
            delta = node.cap
            while node is not self.source:
                node.par.cap = 1
                node.par.rev.cap = 0
                node = node.par.to
            flow += 1
        return flow

import sys
input = sys.stdin.readline

N, M, E = map(int, input().split())
bm = BipartiteMatching(N, M)
for _ in range(E):
    x, y = map(int, input().split())
    bm.add(x, y)
print(bm.maximum_matching())

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    X,Y,E = LI()

    edge = [set() for _ in range(X+Y+2)]

    for _ in range(E):
        a,b = LI()
        i = a + 1
        j = b + X + 1
        edge[i].add(j)
    for i in range(1,X+1):
        edge[0].add(i)
    for j in range(X+1,X+Y+1):
        edge[j].add(X+Y+1)

    ans = 0
    while True:
        node = [-2] * (X + Y + 2)
        node[0] = -1
        q = collections.deque()
        q.append(0)
        while q:
            u = q.pop()
            for v in edge[u]:
                if v == X + Y + 1:
                    ans += 1
                    node[v] = u
                    break
                if node[v] < -1:
                    node[v] = u
                    q.append(v)
            else:
                continue
            break
        else:
            break

        u = X + Y + 1
        while node[u] >= 0:
            edge[node[u]].remove(u)
            edge[u].add(node[u])
            u = node[u]


    print(ans)


if __name__ == '__main__':
    main()