| 18 | return True if visited[t] else False |
| 19 | |
| 20 | def mincut(graph, source, sink): |
| 21 | # This array is filled by BFS and to store path |
| 22 | parent = [-1]*(len(graph)) |
| 23 | max_flow = 0 |
| 24 | res = [] |
| 25 | temp = [i[:] for i in graph] # Record orignial cut, copy. |
| 26 | while BFS(graph, source, sink, parent) : |
| 27 | path_flow = float("Inf") |
| 28 | s = sink |
| 29 | |
| 30 | while(s != source): |
| 31 | # Find the minimum value in select path |
| 32 | path_flow = min (path_flow, graph[parent[s]][s]) |
| 33 | s = parent[s] |
| 34 | |
| 35 | max_flow += path_flow |
| 36 | v = sink |
| 37 | |
| 38 | while(v != source): |
| 39 | u = parent[v] |
| 40 | graph[u][v] -= path_flow |
| 41 | graph[v][u] += path_flow |
| 42 | v = parent[v] |
| 43 | |
| 44 | for i in range(len(graph)): |
| 45 | for j in range(len(graph[0])): |
| 46 | if graph[i][j] == 0 and temp[i][j] > 0: |
| 47 | res.append((i,j)) |
| 48 | |
| 49 | return res |
| 50 | |
| 51 | graph = [[0, 16, 13, 0, 0, 0], |
| 52 | [0, 0, 10 ,12, 0, 0], |