# Kuhn's algorithm

Apr 20th, 2017
569
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import core.bitop;
2. import std.algorithm;
3. import std.array;
4. import std.container;
5. import std.conv;
6. import std.exception;
7. import std.functional;
8. import std.math;
9. import std.numeric;
10. import std.range;
11. import std.stdio;
12. import std.string;
13. import std.typecons;
14. import std.file;
15. import std.bigint;
16.
18.
19. alias pair = Tuple !(int, "l", int, "r");
20.
21. int[][] e;
22. int[] pr, used;
23. pair[] ans;
24.
25. int timer = 1;
26.
27. bool dfs(int st){
28.     used[st] = timer;
29.     foreach (to; e[st]){
30.         if (pr[to] == -1 || (used[pr[to]] < timer && dfs(pr[to]))){
31.             pr[to] = st;
32.             return true;
33.         }
34.     }
35.     return false;
36. }
37.
38. void main(){
39.     File fin = File(TASK ~ ".in", "r");
40.     File fout = File(TASK ~ ".out", "w");
41.     int n, m;
44.     e = new int[][](n, 0);
45.     foreach (i; 0..n){
46.         e[i] = fin.readln.split.map !(to !(int)).array;
47.         e[i] = e[i][0..e[i].length - 1];
48.         e[i][] -= 1;
49.     }
50.     pr = new int[m];
51.     used = new int[n];
52.     pr[] -= 1;
53.     foreach (v; 0..n){
54.         if (dfs(v))
55.             ++timer;
56.     }
57.     ans = new pair[0];
58.     foreach (i; 0..m){
59.         if (pr[i] != -1){
60.             ans ~= pair(pr[i] + 1, i + 1);
61.         }
62.     }
63.     fout.writeln(ans.length);
64.     foreach (a; ans){
65.         fout.writeln(a.l, " ", a.r);
66.     }
67. }
RAW Paste Data