-
Notifications
You must be signed in to change notification settings - Fork 0
Bipartite matching : Kuhn's algorithm
Yessine Jallouli edited this page Jun 20, 2024
·
2 revisions
int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<bool> used;
bool try_kuhn(int v) {
if (used[v])
return false;
used[v] = true;
for (int to : g[v]) {
if (mt[to] == -1 || try_kuhn(mt[to])) {
mt[to] = v;
return true;
}
}
return false;
}
int main() {
//... reading the graph ...
mt.assign(k, -1);
for (int v = 0; v < n; ++v) {
used.assign(n, false);
try_kuhn(v);
}
for (int i = 0; i < k; ++i)
if (mt[i] != -1)
printf("%d %d\n", mt[i] + 1, i + 1);
}
Problems :
https://codeforces.com/group/YTYmnVxV00/contest/216244/problem/G
https://codeforces.com/gym/101485/attachments (Problem E)
Video :
https://www.youtube.com/watch?v=4VYVnEcLZpQ