Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int N = 300005;
- int curcol, used[N], covered[N], match[N];
- vector<int> g[N];
- bool dfs(int v)
- {
- used[v] = curcol;
- for (int u : g[v])
- if (match[u] == -1)
- {
- covered[v] = 1;
- match[u] = v;
- return 1;
- }
- for (int u : g[v])
- if (used[match[u]] != curcol && dfs(match[u]))
- {
- covered[v] = 1;
- match[u] = v;
- return 1;
- }
- return 0;
- }
- void kuhn(int n)
- {
- curcol = 0;
- for (int i = 0; i < n; i++)
- used[i] = 0, match[i] = -1, covered[i] = 0;
- while (true)
- {
- curcol++;
- bool ch = 0;
- for (int i = 0; i < n; i++)
- if (!covered[i] && used[i] != curcol)
- ch |= dfs(i);
- if (!ch)
- break;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement