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:
def outer(x,match,phi):
    if(match[x]==x or phi[match[x]]!=match[x]):
        return True
    return False
    
def inner(x,match,phi):
    if(match[x]!=x and phi[match[x]]==match[x] and phi[x]!=x):
        return True
    return False

def F(x,match,phi):
    if(match[x]!=x and phi[match[x]]==match[x] and phi[x]==x):
        return True
    return False
       
def disjoint(x,y,V,phi,match):
    usedx=[False]*V
    prex=match[x]
    while not (usedx[x] and usedx[prex]) :
        usedx[prex]=True
        usedx[x]=True
        x=phi[prex]
        prex=match[x]
    usedy=[False]*V
    prey=match[y]
    while not (usedy[y] and usedy[prey]) :
        usedy[y]=True
        usedy[prey]=True
        if usedx[y] or usedx[prey]:
            return False
        prey=match[y]
        y=phi[prey]
    return True
    
def shrink(x,y,match,rho,phi,V):
    r=firstvertex(x,y,match,phi,rho,V)
    v=match[x]    
    if x!=r and x!=v:
        while True:
            if rho[phi[v]]!=r:
                phi[phi[v]]=v
            if(phi[v]==r or match[phi[v]]==r):
                break
            v=match[phi[v]]
    v=match[y]
    if y!=r and y!=v:
        while True:
            if rho[phi[v]]!=r:
                phi[phi[v]]=v
            if(phi[v]==r or match[phi[v]]==r):
                break
            v=match[phi[v]]
#             print(y,v,phi[v],r)
    if rho[x]!=r:
        phi[x]=y
    if rho[y]!=r:
        phi[y]=x
        
    used=[False]*V
    used[r]=True
    while x!=r or y!=r: 
        used[x]=True
        used[y]=True
        if(x!=r):
            x=match[x]
        if y!=r:
            y=match[y]
        used[x]=True
        used[y]=True
        if x!=r:
            x=phi[x]
        if y!=r:
            y=phi[y]
    for i in range(V):
        if used[rho[i]] :
            rho[i]=r
    
def firstvertex(x,y,match,phi,rho,V):
    usedx=[False]*V
    usedy=[False]*V
    flag=True
    while True:
        if usedy[x] and rho[x]==x:
            return x
        usedx[x]=True
        if usedx[y] and rho[y]==y:
            return y
        usedy[y]=True
        if flag:
            x=match[x]
            y=match[y]
            flag=False
        else:
            x=phi[x]
            y=phi[y]
            flag=True
       
def augment(x,y,match,phi,V):
    v=match[x]
    used=[False]*V
    used[x]=True
    while not used[v]:
        used[v]=True
        used[phi[v]]=True
        tmp=match[phi[v]]
        match[phi[v]]=v
        match[v]=phi[v]
        v=tmp
    v=match[y]
    used=[False]*V
    used[y]=True
    while not used[v]:
        used[v]=True
        used[phi[v]]=True
        tmp=match[phi[v]]
        match[phi[v]]=v
        match[v]=phi[v]
        v=tmp
    match[x]=y
    match[y]=x
    
    
def Edmonds(graph,V):
    match=[i for i in range(V)]
    phi=[i for i in range(V)]
    rho=[i for i in range(V)]
    scanned=[False]*V
    
    while True:
#         from IPython.core.debugger import Pdb; Pdb().set_trace()
        flag=True
        for i in range(V):
            if (not scanned[i]) and outer(i,match,phi):
                x=i
                flag=False
                break
        if flag:
            break
        for y in graph[x]:
            if F(y,match,phi):
                #拡大
                phi[y]=x
                continue
            if not(outer(y,match,phi) and rho[y]!=rho[x]):
                continue
                
            if disjoint(x,y,V,phi,match):
                #増加
                augment(x,y,match,phi,V)
                scanned=[False]*V
                rho=[i for i in range(V)]
                phi=[i for i in range(V)]
                flag=True
                break
            #縮小
            shrink(x,y,match,rho,phi,V)
        if not flag:
            scanned[x]=True
    cnt=0
    for i in range(V):
        if match[i]!=i:
            cnt+=1
#     print(match)
    return int(cnt/2)
        




x,y,e=list(map(int,input().split()))
v=x+y
graph=[[]for _ in range(v)]

for i in range(e):
    tmp1,tmp2=list(map(int,input().split()))
    tmp2+=x
    graph[tmp1].append(tmp2)
    graph[tmp2].append(tmp1)

cnt=Edmonds(graph,v)
print(cnt)

Submission status: Accepted

Solution code:

class Dinic:
    def __init__(self, len_X, len_Y):
        self.len_X, self.len_Y = len_X, len_Y
        self.edges = [[] for _ in range(len_X)]
        self.matched = [-1] * len_Y
        self.visited = set()

    def add_edge(self, x, y):
        self.edges[x].append(y)

    def dfs(self, x):
        """
        :param x: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for next_x in self.edges[x]:
            if next_x in self.visited:
                continue
            self.visited.add(next_x)
            if self.matched[next_x] == -1 or self.dfs(self.matched[next_x]):
                self.matched[next_x] = x
                return True
        return False

    def solve(self):
        res = 0
        for x in range(self.len_X):
            self.visited = set()
            res += self.dfs(x)
        return res

#################################################################################################


len_X, len_Y, E = map(int, input().split())     # len_X, len_Y: 部分集合に含まれる頂点の数　E: 辺の数


dinic = Dinic(len_X, len_Y)

for _ in range(E):
    x, y = map(int, input().split())
    dinic.add_edge(x,y)

# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(dinic.solve())

Submission status: Accepted

Solution code:
# AOJ GRL_7_A "Bipartite Matching"
# O(VE)

class BipartiteMatching():
    def __init__(self, V1, V2):
        self.V1 = V1
        self.V2 = V2
        self.V = V1 + V2
        self.graph = [[] for _ in range(V1+V2)]
    
    def add_edge(self, v1, v2):
        v2 += self.V1
        self.graph[v1].append(v2)
        self.graph[v2].append(v1)

    # search increasing path
    def dfs(self, s):
        self.par = [None]*self.V
        self.used = [False]*self.V
        self.used[s] = True
        self.stack = [s]
        while self.stack:
            v = self.stack.pop()
            for nv in self.graph[v]:
                w = self.match[nv]
                if w < 0:
                    while True:
                        self.match[v] = nv
                        self.match[nv] = v
                        if v == s: return True
                        v, nv = self.par[v]
                elif not self.used[w]:
                    self.par[w] = (v, nv)
                    self.used[w] = True
                    self.stack.append(w)
        return False

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


if __name__ == '__main__':
    import sys
    input = sys.stdin.readline

    V1, V2, E = map(int, input().split())
    bm = BipartiteMatching(V1, V2)
    for _ in range(E):
        a, b = map(int, input().split())
        bm.add_edge(a, b)
    print(bm.bipartite_matching())

Submission status: Accepted

Solution code:
import sys,collections
sys.setrecursionlimit(100000)

INF = float("inf")

X,Y,E = map(int,sys.stdin.readline().split())
xy = tuple(tuple(map(int,sys.stdin.readline().rstrip().split())) for _ in range(E)) # multi line with multi param
#uvc = [[0,1,1],[0,2,3],[1,2,1],[2,3,2]]
V = X+Y+2
uvc = [[x+1,y+X+1,1] for x,y in xy]
for i in range(X):
    uvc.append([0,i+1,1])
for i in range(Y):
    uvc.append([X+i+1,V-1,1])
G = {i:{} for i in range(V)}
mG = {i:{} for i in range(V)}

for u,v,c in uvc:
    G[u][v] = c
    G[v][u] = 0 # reverse edge
    mG[u][v] = 0
    mG[v][u] = 0
# print(G)
# print(mG)
def dfs(current,flow):
    if current == V-1:
        return flow
    visited.add(current)
    for nex,nex_c in G[current].items():
        if not nex in visited and nex_c != 0:
            f = dfs(nex,min(flow,nex_c))
            if f != 0:
                mG[current][nex] = mG[current][nex] + f
                G[current][nex] = G[current][nex] - f
                G[nex][current] = G[nex][current] + f
                return f
    return 0

visited = set()
while dfs(0,INF) != 0:
    visited = set()
    # print("mG:",mG)
    # print("G:",G)
    pass
print(sum(mG[0].values()))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, v, inf=10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v  # 深さ
        self.ite = [0]*v  # DFSでの探索が済んでいるか
    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 bfs(self, s):  # BFSで深さ決定,sがstart
        self.level = [-1]*self.v  # 必要
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0: ###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])
    def dfs(self, v, t, f):  # DFSで増加パス探索,v開始、t終点、総フローf
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d>0:
                    e[1] -= d  # cap減少
                    self.G[e[0]][e[2]][1] += d  # 逆辺のcap増加
                    return d
        return 0
    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v  # DFSでの探索が済んでいるか否か
            f = self.dfs(s,t,self.inf)
            while f>0:
                flow += f
                f = self.dfs(s,t,self.inf)

X, Y, E = MAP()
D = Dinic(X+Y+2)
s = X+Y
t = X+Y+1

for i in range(X):
	D.add_edge(s, i, 1)

for i in range(Y):
	D.add_edge(X+i, t, 1)

for _ in range(E):
	x, y = MAP()
	D.add_edge(x, X+y, 1)

print(D.max_flow(s, t))

Submission status: Accepted

Solution code:
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

x,y,e = map(int, input().split())
s = x+y
t = x+y+1
dinic = Dinic(x+y+2)

for _ in range(e):
    xv,yv = map(int, input().split())
    dinic.add_edge(xv,x+yv,1)

for xv in range(x):
    dinic.add_edge(s,xv,1)
for yv in range(x,x+y):
    dinic.add_edge(yv,t,1)

print(dinic.flow(s,t))

Submission status: Accepted

Solution code:
from collections import deque

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

    def __init__(self,n,inf = 10**9+7):
        self.n = n
        self.inf = inf
        self.level = [-1]*n
        self.iter = [0]*n
        self.e = [[] for _ in range(n)]

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

    def bfs(self, start):
        self.level = [-1]*self.n
        dq = deque()
        self.level[start] = 0
        dq.append(start)
        while dq:
            cur_vertex = dq.popleft()
            for edge in self.e[cur_vertex]:
                if edge.cap > 0 > self.level[edge.to]:
                    self.level[edge.to] = self.level[cur_vertex] + 1
                    dq.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:return flow
        while self.iter[cur_vertex] < len(self.e[cur_vertex]):
            edge = self.e[cur_vertex][self.iter[cur_vertex]]
            if edge.cap > 0 and self.level[cur_vertex] < self.level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self.e[edge.to][edge.rev].cap += flowed
                    return flowed
            self.iter[cur_vertex] += 1
        return 0

    def compute(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:return flow
            self.iter = [0]*self.n
            while True:
                f = self.dfs(source, sink, self.inf)
                if f == 0:break
                flow += f

def main():
    x,y,e = map(int,input().split())
    mf = MaxFlow(x+y+2)
    s = x+y
    t = s+1
    for _ in range(e):
        a,b = map(int,input().split())
        mf.add_edge(a,b+x,1)
    for i in range(x):
        mf.add_edge(s,i,1)
    for i in range(y):
        mf.add_edge(i+x,t,1)
    print (mf.compute(s,t))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque

class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0; self.N1 = N1
        self.N = N = 2 + N0 + N1
        self.E = E = [[] for _ in range(N)]
        for end in range(N0): # vertex 0 is the source
            v = end + 2
            E[0].append([v, 1, len(E[v])])
            E[v].append([0, 0, len(E[0]) - 1])
        for init in range(N1): # vertex 1 is the sink
            u = init + N0 + 2
            E[u].append([1, 1, len(E[1])])
            E[1].append([u, 0, len(E[u]) - 1])
    
    def add_edge(self, p1, p2):
        '''
            e[0] = the head vertex of e,
            e[1] = current capacity of e,
            e[2] = the index of reverse edge of e.
        '''
        p1 += 2; p2 += self.N0 + 2
        self.E[p1].append([p2, 1, len(self.E[p2])])
        self.E[p2].append([p1, 0, len(self.E[p1]) - 1])
    
    def _exist_augpath(self):
        self.level = level = [-1] * self.N # the level (depth) of each vertex
        E = self.E
        q = deque([(0, 0)]) # (vertex, level)
        while q:
            v, lv = q.popleft()
            if level[v] < 0: # visited v for the first time
                level[v] = lv
                for u, cap, _ in E[v]:
                    if cap == 0 or level[u] >= 0: continue
                    q.append((u, lv + 1))
        return level[1] >= 0
    
    def _blocking_flow(self):
        s = 0; t = 1
        aug_flow = 0
        finished = [False] * self.N
        parent = [-1] * self.N
        revs = [-1] * self.N
        bottleneck = -1; temp_flow = 0
        level, E = self.level, self.E
        stack = [(s, -1, float('inf'), -1, 0)] # (vertex, parent, flow, rev_idx, status)
        while stack:
            v, p, f, rev, st = stack.pop()
            if temp_flow and v != bottleneck: continue
            if st == 0 and not finished[v]:
                parent[v] = p; revs[v] = rev
                if temp_flow: # offset
                    f -= temp_flow; temp_flow = 0; bottleneck = -1
                if v == t: # an augment path is found
                    aug_flow += f
                    if p != -1: stack += [(v, p, f, rev, 3)]
                    continue
                n_children = 0
                for u, cap, rev_idx in E[v]:
                    if cap == 0 or finished[u] or level[u] != level[v] + 1: continue
                    if n_children == 0:
                        stack += [(v, p, 0, rev, 2), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                    else:
                        stack += [(v, p, 0, rev, 1), (u, v, min(f, cap), rev_idx, 0)]
                        n_children += 1
                if n_children == 0: # v is a leaf
                    finished[v] = True
            elif st == 1: # now searching
                continue
            elif st == 2: # search finished
                finished[v] = True
            else: # edge update
                rev_e = E[v][rev]; e = E[p][rev_e[2]]
                e[1] -= f; rev_e[1] += f
                if e[1] == 0: bottleneck = p
                if parent[p] != -1: stack += [(p, parent[p], f, revs[p], 3)]
                else: temp_flow = f
        return aug_flow
    
    def max_matching(self):
        matching = 0
        exist_augpath, blocking_flow = self._exist_augpath, self._blocking_flow
        while True:
            if not exist_augpath(): break
            matching += blocking_flow()
        return matching

N0, N1, M = map(int, input().split())
hk = HopcroftKarp(N0, N1)
for _ in range(M):
    u, v = map(int, input().split())
    hk.add_edge(u, v)
print(hk.max_matching())

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BipartiteMatching:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.pairA = [-1] * N
        self.pairB = [-1] * M
        self.edge = [[] for _ in range(N)]
        self.was = [0] * N
        self.iter = 0

    def add(self, s, t):
        self.edge[s].append(t)

    def _DFS(self, s):
        self.was[s] = self.iter
        for t in self.edge[s]:
            if self.pairB[t] == -1:
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        for t in self.edge[s]:
            if self.was[self.pairB[t]] != self.iter and self._DFS(self.pairB[t]):
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        return False

    def solve(self):
        res = 0
        while True:
            self.iter += 1
            found = 0
            for i in range(self.N):
                if self.pairA[i] == -1 and self._DFS(i):
                    found += 1
            if not found:
                break
            res += found
        return res


if __name__ == "__main__":
    X, Y, E = map(int, input().split())
    match = BipartiteMatching(X, Y)
    for _ in range(E):
        x, y = map(int, input().split())
        match.add(x, y)
    ans = match.solve()
    print(ans)

Submission status: Accepted

Solution code:
#フローに帰着、dinic法,dinic法は蟻本
import sys
from collections import deque

sys.setrecursionlimit(200000)

class Dinic:
    
    def __init__(self,v, inf =10**10):
        self.v = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [-1]*v#深さ
        self.ite = [0]*v#DFSでの探索が済んでいるか否か
    
    def add_edge(self, fr, to, cap):#末尾はself.G[to]から対応する辺のself.G[fr]内でのindex
        self.G[fr].append([to,cap,len(self.G[to])])###{'to':to,"cap":cap,"rev";len(self.G[to})}みたいにしたほうがいいか
        self.G[to].append([fr,0,len(self.G[fr])-1])

    
    def bfs(self,s):#BFSで深さ決定,sがstart
        self.level = [-1]*self.v#必要
        self.level[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            v = Q.popleft()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e[1]>0 and self.level[e[0]]<0:###capacity>0かつtoの深さ未定
                    self.level[e[0]] = self.level[v]+1
                    Q.append(e[0])

        
    def dfs(self,v,t,f):#DFSで増加パス探索,v開始、t終点、総フローf
        if v==t:
            return f
        for i in range(self.ite[v],len(self.G[v])):
            self.ite[v] = i
            e = self.G[v][i]
            if e[1]>0 and self.level[v]<self.level[e[0]]:
                d = self.dfs(e[0],t,min(f,e[1]))
                if d>0:
                    e[1] -= d #cap減少
                    self.G[e[0]][e[2]][1] += d#逆辺のcap増加
                    return d
        return 0
    
    def max_flow(self,s,t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t]<0:
                return flow
            self.ite = [0]*self.v#DFSでの探索が済んでいるか否か
            f =self.dfs(s,t,self.inf)
            while f>0:
                flow+= f
                f = self.dfs(s,t,self.inf)
            
x,y,e = map(int, input().split( ))
D = Dinic(x+y+2)
for _ in range(e):
    u,w = map(int, input().split( ))
    D.add_edge(u,w+x,1)
for i in range(x+y):
    if i<x:
        D.add_edge(x+y,i,1)
    else:
        D.add_edge(i,x+y+1,1)
ans = D.max_flow(x+y,x+y+1)
print(ans)

Submission status: Accepted

Solution code:
from typing import Set


def dfs(s: int) -> bool:
    return _dfs(s, set())


def _dfs(v: int, visited: Set[int]) -> bool:
    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


if __name__ == "__main__":
    xn, yn, e = map(lambda x: int(x), input().split())
    edges = [set() for _ in range(xn)]  # type: ignore
    matched = [-1] * yn

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

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

Submission status: Accepted

Solution code:
from collections import deque


class Bipartite_Matching:
    """二部グラフの最大マッチングを求めるなどする"""

    def __init__(self, input_graph: list):
        """重み無し二部グラフinput_graphを入力する"""
        n = len(input_graph)
        self.INF = float("inf")
        # DFSでグラフを2色に彩色する
        visited = [-1] * n
        for i in range(n):
            if visited[i] >= 0:
                continue
            visited[i] = 0
            q = deque([i]) 
            while q:
                _from = q.pop()
                for to in input_graph[_from]:
                    if visited[to] >= 0:
                        continue
                    visited[to] = visited[_from] ^ 1
                    q.append(to)

        # 残余グラフを構築する
        self.s = n
        self.t = n + 1
        self.n = n + 2
        self.graph = [[] for i in range(self.n)]
        used = set([])
        for pos1 in range(n):
            if visited[pos1] == 0:
                self.add_edge(self.s, pos1)
            else:
                self.add_edge(pos1, self.t)
            for pos2 in input_graph[pos1]:
                if (min(pos1, pos2), max(pos1, pos2)) in used:
                    continue
                used.add((min(pos1, pos2), max(pos1, pos2)))
                if visited[pos1] == 0:
                    self.add_edge(pos1, pos2)
                else:
                    self.add_edge(pos2, pos1)
 
    def add_edge(self, _from: int, to: int):
        """残余グラフを構築
        1. _fromからtoへ向かう容量capacity = 1の辺をグラフに追加する
        2. toから_fromへ向かう容量0の辺をグラフに追加する
        """
        forward = [to, 1, None]
        forward[2] = backward = [_from, 0, forward]
        self.graph[_from].append(forward)
        self.graph[to].append(backward)
 
    def bfs(self, s: int, t: int):
        """capacityが正の辺のみを通ってsからtに移動可能かどうかBFSで探索
        level: sからの最短路の長さ
        """
        self.level = [-1] * self.n
        q = deque([s])
        self.level[s] = 0
        while q:
            _from = q.popleft()
            for to, capacity, _ in self.graph[_from]:
                if capacity > 0 and self.level[to] < 0:
                    self.level[to] = self.level[_from] + 1
                    q.append(to)
 
    def dfs(self, _from: int, t: int, f: int) -> int:
        """流量が増加するパスをDFSで探索
        BFSによって作られた最短路に従ってfを更新する
        """
        if _from == t:
            return f
        for edge in self.itr[_from]:
            to, capacity, reverse_edge = edge
            if capacity > 0 and self.level[_from] < self.level[to]:
                d = self.dfs(to, t, min(f, capacity))
                if d > 0:
                    edge[1] -= d
                    reverse_edge[1] += d
                    return d
        return 0
 
    def max_flow(self):
        """s-tパス上の最大流を求める = 最大マッチングを求める
        計算量: O(|E||V|^2)
        """
        flow = 0
        while True:
            self.bfs(self.s, self.t)
            if self.level[self.t] < 0:
                break
            self.itr = list(map(iter, self.graph))
            f = self.dfs(self.s, self.t, self.INF)
            while f > 0:
                flow += f
                f = self.dfs(self.s, self.t, self.INF)
        return flow


x, y, e = map(int, input().split())
graph = [[] for i in range(x + y)]

for i in range(e):
    tmp_x, tmp_y = map(int, input().split())
    graph[tmp_x].append(tmp_y + x)
    graph[tmp_y + x].append(tmp_x)

mb = Bipartite_Matching(graph)
print(mb.max_flow())

Submission status: Accepted

Solution code:
import collections
import queue


class Dinic:
    def __init__(self, N):
        self.N = N
        self.edges = collections.defaultdict(list)
        self.level = [0 for _ in range(self.N)]
        self.iter = [0 for _ in range(self.N)]

    def add(self, u, v, c, directed=True):
        """
        0-indexed
        u = from, v = to, c = cap
        directed = Trueなら、有向グラフである
        """
        if directed:
            self.edges[u].append([v, c, len(self.edges[v])])
            self.edges[v].append([u, 0, len(self.edges[u])-1])
        else:  # TODO
            self.edges[u].append([v, c, len(self.edges[u])])

    def bfs(self, s):
        self.level = [-1 for _ in range(self.N)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get(s)
            for i in range(len(self.edges[v])):
                e = self.edges[v][i]
                if e[1] > 0 and self.level[e[0]] < 0:
                    self.level[e[0]] = self.level[v] + 1
                    que.put(e[0])

    def dfs(self, v, t, f):
        if v == t:
            return f
        for i in range(self.iter[v], len(self.edges[v])):
            self.iter[v] = i
            e = self.edges[v][i]
            if e[1] > 0 and self.level[v] < self.level[e[0]]:
                d = self.dfs(e[0], t, min(f, e[1]))
                if d > 0:
                    e[1] -= d
                    self.edges[e[0]][e[2]][1] += d
                    return d
        return 0

    def maxFlow(self, s, t):
        flow = 0
        while True:
            self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iter = [0 for _ in range(self.N)]
            f = self.dfs(s, t, float('inf'))
            while f > 0:
                flow += f
                f = self.dfs(s, t, float('inf'))


X, Y, E = map(int, input().split())

graph = Dinic(X+Y+2)
s = X+Y
t = X+Y+1
for i in range(X):
    graph.add(s, i, 1)

for i in range(Y):
    graph.add(X+i, t, 1)

for _ in range(E):
    x, y = map(int, input().split())
    graph.add(x, X+y, 1)

print(graph.maxFlow(s, t))

Submission status: Accepted

Solution code:
class BipartiteMatching:
    def __init__(self, v: int):
        self.v = v
        self.g = [[] for _ in range(v)]
        self.match = [-1] * v
        self.used = [False] * v

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

    def dfs(self, v):
        self.used[v] = True
        for i in range(len(self.g[v])):
            u = self.g[v][i]
            w = self.match[u]

            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 maximum_matching(self):
        res = 0
        self.match = [-1] * self.v
        for i in range(self.v):
            if self.match[i] < 0:
                self.used = [False] * self.v
                if self.dfs(i):
                    res += 1
        return res


if __name__ == '__main__':
    x_size, y_size, e = map(int, input().split())
    b = BipartiteMatching(x_size + y_size)
    for i in range(e):
        x, y = map(int, input().split())
        b.add_edge(x, y + x_size)
    print(b.maximum_matching())