# pastebin

Paste Search Dynamic
Recent pastes
find path
1. def find_path(s, t, graph, path=[]):
2.
3.         new_path = path.copy()
4.         new_path.append(s)
5.         if s == t:
6.                 return new_path
7.         for next_node in graph[s].keys():
8.                 if next_node not in new_path:
9.                         return find_path(next_node, t, graph, new_path)
10.         return []
11.
12.
13. def find_flow(path, graph):
14.
15.         flow = float('inf')
16.         for i in range(1,len(path)):
17.                 curr_node = path[i-1]
18.                 next_node = path[i]
19.                 capacity = graph[curr_node][next_node]
20.                 flow = min(flow, capacity)
21.         return flow
22.
23. def update_graph(path, flow, graph):
24.
25.         for i in range(1,len(path)):
26.                 curr_node = path[i-1]
27.                 next_node = path[i]
28.                 graph[curr_node][next_node] -= flow
29.                 if graph[curr_node][next_node] == 0:
30.                         graph[curr_node].pop(next_node)
31.                 graph[next_node][curr_node] = graph[next_node].get(curr_node,0) + flow
32.
33. for _ in range(int(input())):
34.
35.         inputs = input().split()
36.         m, n, q = int(inputs[0]), int(inputs[1]), int(inputs[2])
37.
38.         graph = {i:{} for i in range(0,m+n+2)}
39.
40.         # node 1 to m is set A
41.         # node m+1 to m+n is set B
42.         for _ in range(q):
43.                 inputs = input().split()
44.                 A, B = int(inputs[0]), int(inputs[1])
45.                 graph[A][B+m] = 1
46.
47.         # node 0 is source
48.         # node m+n+1 is sink
49.         for i in range(1,m+1):
50.                 graph[0][i] = 1
51.         for i in range(1,n+1):
52.                 graph[i+m][m+n+1] = 1
53.
54.         max_flow = 0
55.         path = find_path(0, m+n+1, graph)
56.         while(len(path) > 0 and path[-1] == n):
57.                 flow = find_flow(path, graph)
58.                 max_flow += flow
59.                 update_graph(path, flow, graph)
60.                 path = find_path(0, m+n+1, graph)
61.         output = str(max_flow) + " "
62.         output += "Y" if max_flow == m else "N"
63.         print(output)
Parsed in 0.022 seconds