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 ∈ 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|  x 0  y 0  x 1  y 1 : 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.  x i and y i 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

Solution (Python):
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())

Solution (Python):
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
    
    for xi in range(x):
        g[source].append(xi)
        residual[source][xi] = 1
    
    for yi in range(x, x + y):
        g[yi].append(sink)
        residual[yi][sink] = 1
    
    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()

Solution (Python):
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, Ts, Es = read_data()
    print(bp_match(Ss, Ts, Es))

Solution (Python):
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("}")
        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())

Solution (Python):



"""
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())

Solution (Python):



"""
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())

Solution (Python):



"""
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
    
    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())

Solution (Python):



"""
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
    
    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())

Solution (Python):



"""
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
    
    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())

Solution (Python):



"""
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
    
    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())

Solution (Python):



"""
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
    
    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())

Solution (Python):



"""
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
            
            
            
            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
    
    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())

Solution (Python):



"""
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
            
            
            
            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
    
    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())

Solution (Python):



"""
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
            
            
            
            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
    
    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())

Solution (Python):


"""
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())

Solution (Python):


"""
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())

Solution (Python):


"""
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())

Solution (Python):


"""
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())

Solution (Python):


"""
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())

Solution (Python):


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



import collections


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


print(ford_fulkerson(s, t))

Solution (Python):


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



import collections


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]


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]
        
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(v_num)]
    return max_flow


print(dinic(s, t))

Solution (Python):


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



import collections


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]


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]
        
        dfs(source, path, parent, blocking_flow)
        max_flow += blocking_flow[0]
        parent = [[] for i in range(v_num)]
    return max_flow


print(dinic(s, t))

Solution (Python):
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)