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:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def FordFulkerson(S,T): #sからFord-Fulkerson
    global lines
    global cost
    global ans

    queue = deque()     #BFS用のdeque
    queue.append([S,INF])
    ed = [True]*N    #到達済み
    ed[S] = False
    route = [0 for i in range(N)]   #ルート
    route[S] = -1

    #BFS
    while queue:
        s,flow = queue.pop()
        for t in lines[s]:  #s->t
            if ed[t]:
                flow = min(cost[s][t],flow)  #flow = min(直前のflow,line容量)
                route[t] = s
                queue.append([t,flow])
                ed[t] = False
                if t == T: #ゴール到達
                    ans += flow
                    break
        else:
            continue
        break
    else:
        return False

    #ラインの更新
    t = T
    s = route[t]
    while s != -1:
        #s->tのコスト減少，ゼロになるなら辺を削除
        cost[s][t] -= flow
        if cost[s][t] == 0:
            lines[s].remove(t)

        #t->s(逆順)のコスト増加，元がゼロなら辺を作成
        if cost[t][s] == 0:
            lines[t].add(s)
        cost[t][s] += flow

        t = s
        s = route[t]
    return True

def PrimeFactoring(x):
    p = 2
    primes = []
    while x >= 2:
        if x%p == 0:
            primes.append(p)
            x //= p
            p = 2
        else:
            p += 1
    return primes

while True:
    X,Y,M = inpl()
    lines = defaultdict(set)
    N = X+Y+2
    S = X+Y
    T = X+Y+1
    cost = [[0]*N for _ in range(N)]

    for i in range(M):
        x,y = inpl()
        lines[x].add(y+X)
        cost[x][y+X] = 1
        
    for i in range(X):
        lines[S].add(i)
        cost[S][i] = 1
    for i in range(Y):
        lines[i+X].add(T)
        cost[i+X][T] = 1

    ans = 0

    while FordFulkerson(S,T):
        pass

    print(ans)

    break

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)
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()))
INF=float('inf')

class BipartiteMatching:
    """
    XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
    edges[x]: xとつながるYの頂点のset
    match1[x]: xとマッチングされたYの頂点
    match2[y]: yとマッチングされたXの頂点
    """

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

    def whois1(self, a):
        """ :param: グループ1の頂点 :return: ペアになるグループ2の頂点 """
        return self.match1[a]

    def whois2(self, a):
        """ :param: グループ2の頂点 :return: ペアになるグループ1の頂点 """
        return self.match2[a]

    def solve(self):
        # 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
        return sum(self.dfs(i, set()) for i in range(self.n))

N,M,E=MAP()
bm=BipartiteMatching(N, M)
for i in range(E):
    x,y=MAP()
    bm.add(x, y)

print(bm.solve())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

# 1:shortest path
# 1_A
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
                print(dist, q)
    return dist

v,e,r = map(int, input().split(" "))
adj = [[] for i in range(v)]
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj[s].append([t, d])
lis = dijkstra(v, r)
print(lis)
for i in lis:
    print(str(i).upper())
"""

# 1_B
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
                if dist[k] > dist[j] + l:
                    dist[k] = dist[j] + l
                    update = True
                    if i == num-1:
                        return False
        if not update:
            break
    return dist

v,e,r = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t,d = map(int, input().split(" "))
    adj.append([s, t, d])
lis = bellman_ford(v, r)
if not lis:
    print("NEGATIVE CYCLE")
else:
    for i in lis:
        print(str(i).upper())
"""

# 1_C
"""
def warshallfloyd(n):
    for i in range(n):
        for j in range(n):
            for k in range(n):
                d[j][k] = min(d[j][k], d[j][i]+d[i][k])
v,e = map(int, input().split())
d = [[float("inf") for j in range(v)] for i in range(v)]
for i in range(v):
    d[i][i] = 0
for i in range(e):
    s, t, c = map(int, input().split())
    d[s][t] = c
warshallfloyd(v)
for i in range(v):
    if d[i][i] < 0:
        print("NEGATIVE CYCLE")
        quit()
for i in d:
    for j in range(v):
        if j < v-1:
            print(str(i[j]).upper(), end = " ")
        else:
            print(str(i[j]).upper())
"""

# 2:spanning tree
# 2_A
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
v,e = LI()
c = LIR(e)
c.sort(key = lambda x:x[2])
par = [i for i in range(v)]
rank = [0 for i in range(v)]
k = 0
ans = 0
for a,b,w in c:
    if not same(a,b):
        k += 1
        unite(a,b)
        ans += w
    if k == v-1:
        break
print(ans)
"""

#2_B
"""
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

def same(x,y):
    return root(x) == root(y)

def unite(x,y):
    x = root(x)
    y = root(y)
    if rank(x) < rank(y):
        par[x] = y
    else:
        par[y] = x
        if rank(x) == rank(y):
            rank[x] += 1
"""

#3:connected components
#3_A

#3_B

#3_C


#4:path/cycle
#4_A
"""
def bellman_ford(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start] = 0
    for i in range(num):
        update = False
        for j, k, l in adj:
            if dist[k] > dist[j] + l:
                dist[k] = dist[j] + l
                update = True
                if i == num-1:
                    return False
        if not update:
            break
    return True

v, e = map(int, input().split(" "))
adj = []
for i in range(e):
    s,t = map(int, input().split(" "))
    adj.append([s, t, -1])
for i in range(v):
    if not bellman_ford(v,i):
        print(1)
        quit()
print(0)
"""

#4_B


#5:tree
#5_A
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = II()
adj = [[] for i in range(n)]
for i in range(n-1):
    s,t,w = LI()
    adj[s].append([t, w])
    adj[t].append([s, w])
d = dijkstra(n,0)
i = d.index(max(d))
d2 = dijkstra(n,i)
print(max(d2))
"""

#5_B
"""
from heapq import heappush, heappop
def dijkstra(num, start):
    dist = [float("inf") for i in range(num)]
    dist[start]  = 0
    q = [[dist[start], start]]
    while q:
        du, u = heappop(q)
        for j, k in adj[u]:
            if dist[j] > du + k:
                dist[j] = du + k
                heappush(q, [dist[j], j])
    return dist

n = int(input())
adj = [[] for i in range(n)]
for i in range(n-1):
    s, t, w = map(int, input().split(" "))
    adj[s].append([t, w])
    adj[t].append([s, w])
for i in range(n):
    s = dijkstra(n,i)
    print(max(s))
"""
#5_C

#5_D

#5_E


#6
#6_A_maximum_flow
"""
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

n,e = LI()
c = [[0 for i in range(n)] for j in range(n)]
for i in range(e):
    a,b,w = LI()
    if a != n-1:
        c[a][b] = w
print(ford_fulkerson(0,n-1,c,n))
"""
#6_B


#7
#7_A
def bfs(s,g,n):
    bfs_map = [-1 for i in range(n)]
    bfs_map[s] = 0
    q = deque()
    q.append(s)
    fin = False
    while q:
        x = q.popleft()
        for y in range(n):
            if c[x][y] > 0 and bfs_map[y] < 0:
                bfs_map[y] = bfs_map[x]+1
                if y == g:
                    fin = True
                    break
                q.append(y)
        if fin:
            break

    if bfs_map[g] == -1:
        return [None,0]
    path = [None for i in range(bfs_map[g]+1)]
    m = float("inf")
    path[bfs_map[g]] = g
    y = g
    for i in range(bfs_map[g])[::-1]:
        for x in range(n+1):
            if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                path[i] = x
                if c[x][y] < m:
                    m = c[x][y]
                y = x
                break
    return [path,m]

def ford_fulkerson(s,g,c,n):
    while 1:
        p,m = bfs(s,g,n)
        if not m:break
        for i in range(len(p)-1):
            c[p[i]][p[i+1]] -= m
            c[p[i+1]][p[i]] += m
    return sum(c[g])

x,y,e = LI()
c = [[0 for i in range(x+y+2)] for j in range(x+y+2)]
for i in range(x):
    c[0][i+1] = 1
for i in range(y):
    c[x+i+1][x+y+1] = 1
for i in range(e):
    a,b = LI()
    c[a+1][x+b+1] = 1
print(ford_fulkerson(0,x+y+1,c,x+y+2))

Submission status: Accepted

Solution code:
from collections import deque


class Dinic(object):
    __slots__ = ["inf", "v_count", "edges", "iter", "level"]

    def __init__(self, v_count: int, edges: list):
        self.inf = 10**9
        self.v_count = v_count
        self.edges = [[] for _ in [0]*v_count]
        self.iter = [0]*v_count
        self.level = None
        self._create_graph(edges)

    def _create_graph(self, _edges):
        edges = self.edges
        for origin, dest, cap in _edges:
            edges[origin].append([dest, cap, len(edges[dest])])
            edges[dest].append([origin, 0, len(edges[origin])-1])

    def solve(self, source: int, sink: int):
        max_flow = 0

        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return max_flow

            self.iter = [0]*self.v_count
            flow = self.dfs(source, sink, self.inf)

            while flow > 0:
                max_flow += flow
                flow = self.dfs(source, sink, self.inf)

    def bfs(self, source: int):
        level, edges = [-1]*self.v_count, self.edges
        level[source] = 0
        dq = deque([source])
        popleft, append = dq.popleft, dq.append

        while dq:
            v = popleft()
            for dest, cap, _rev in edges[v]:
                if cap > 0 > level[dest]:
                    level[dest] = level[v] + 1
                    append(dest)

        self.level = level

    def dfs(self, source: int, sink: int, flow: int) -> int:
        if source == sink:
            return flow
        while self.iter[source] < len(self.edges[source]):
            dest, cap, rev = edge = self.edges[source][self.iter[source]]
            if cap > 0 and self.level[source] < self.level[dest]:
                flowed = self.dfs(dest, sink, flow if flow < cap else cap)
                if flowed > 0:
                    edge[1] -= flowed
                    self.edges[dest][rev][1] += flowed
                    return flowed
            self.iter[source] += 1

        return 0


if __name__ == "__main__":
    import sys
    X, Y, E = map(int, input().split())
    source, sink = X+Y, X+Y+1
    edges = [(source, i, 1) for i in range(X)] + [(X+i, sink, 1) for i in range(Y)]
    append = edges.append
    for x, y in (map(int, l.split()) for l in sys.stdin):
        append((x, X+y, 1))
    dinic = Dinic(X+Y+2, edges)
    print(dinic.solve(source, sink))

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
        while self._iter[cur_vertex] < len(self._graph[cur_vertex]):
            e = self._graph[cur_vertex][self._iter[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
            self._iter[cur_vertex] += 1
        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:
#!/usr/bin/env python3
# GRL_7_A: Matching - Bipertite Matching


from heapq import heappush, heappop


class Edge:
    __slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

    def __init__(self, v, w, capacity, cost=0):
        self.src = v
        self.dest = w
        self.capacity = capacity
        self.cost = cost
        self.flow = 0

    def other(self, v):
        if v == self.src:
            return self.dest
        else:
            return self.src

    def residual_capacity(self, v):
        if v == self.src:
            return self.capacity - self.flow
        else:
            return self.flow

    def cost_from(self, v):
        if v == self.src:
            return self.cost
        else:
            return -self.cost

    def add_flow(self, v, f):
        if v == self.src:
            self.flow += f
        else:
            self.flow -= f

    def __str__(self):
        return "{} {} {} {} {}".format(self.src, self.dest, self.capacity,
                                       self.cost, self.flow)


class Network:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)
        self._edges[edge.dest].append(edge)

    def adj(self, v):
        return self._edges[v]

    def flow(self, v):
        return sum(e.flow for e in self.adj(v) if e.src == v)

    def cost(self):
        cost = 0
        for v in range(self.v):
            for e in self.adj(v):
                if e.src == v:
                    cost += e.flow * e.cost
        return cost

    def __str__(self):
        s = ''
        for v in range(self.v):
            for e in self.adj(v):
                s += "{} {}\n".format(v, e)

        return s


def max_flow(network, s, t):
    def augment_path():
        marked = [False] * network.v
        edge_to = [None] * network.v
        n = 0
        heap = [(-10**6, s, n, None)]
        while heap:
            cap, v, _, e = heappop(heap)
            edge_to[v] = e
            if v == t:
                return (-cap, edge_to)
            if not marked[v]:
                marked[v] = True
                for ne in network.adj(v):
                    n += 1
                    w = ne.other(v)
                    c = ne.residual_capacity(v)
                    if not marked[w] and c > 0:
                        heappush(heap, (max(-c, cap), w, n, ne))

        return (0, [])

    while True:
        cap, path = augment_path()
        if cap == 0:
            break
        v = t
        e = path[t]
        while e is not None:
            v = e.other(v)
            e.add_flow(v, cap)
            e = path[v]

    return network.flow(s)


def run():
    n, m, e = [int(i) for i in input().split()]
    s, t = 0, n+m+1
    net = Network(n+m+2)
    for i in range(n):
        net.add(Edge(s, i+1, 1))
    for j in range(m):
        net.add(Edge(j+1+n, t, 1))

    for _ in range(e):
        x, y = [int(i) for i in input().split()]
        edge = Edge(x+1, y+1+n, 1)
        net.add(edge)

    print(max_flow(net, s, t))


if __name__ == '__main__':
    run()

Submission status: Accepted

Solution code:
# Hopcroft-Karp Algorithm
from collections import deque
class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        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)
        self.level = level
        return level[1] is not None

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

    def flow(self):
        flow = 0
        N = self.N; G = self.G
        bfs = self.bfs; dfs = self.dfs
        while bfs():
            *self.it, = map(iter, G)
            while dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]


import sys
readline = sys.stdin.readline
write = sys.stdout.write

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

hc = HopcroftKarp(X, Y)
for i in range(E):
    x, y = map(int, readline().split())
    hc.add_edge(x, y)

write("%d\n" % hc.flow())

Submission status: Accepted

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

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

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: Runtime Error

Solution code:
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: Runtime Error

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: Runtime Error

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