Алгоритм Куна — максимальное паросочетание в двудольном графе
Алгоритм Куна — максимальное паросочетание в двудольном графе
Дан двудольный граф с долями:
- левая: ,
- правая: ,
Алгоритм Куна — максимальное паросочетание в двудольном графе
Дан двудольный граф с долями:
Требуется найти наибольшее паросочетание — максимальное множество рёбер, не имеющих общих вершин.
Алгоритм Куна — непосредственное применение теоремы Бержа:
Паросочетание максимально ⇔ в графе нет увеличивающих цепей.
Алгоритм работает так:
Увеличивающая цепь — путь, который:
После чередования рёбер вдоль цепи размер паросочетания увеличивается на 1.
Для вершины левой доли:
То есть:
→ соединяем с
Для всех :
Каждый DFS —
Запускаем до раз:
В худшем случае:
Важно:
int n, k;
vector<vector<int>> g;
vector<int> mt;
vector<char> 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() {
// чтение графа
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) {
cout << mt[i] + 1 << " " << i + 1 << "\n";
}
}
}