Kun algoritmi — ikki ulushli grafda maksimal juftlash
Kun algoritmi — ikki ulushli (bipartite) grafda maksimal juftlashtirish
Ikki bo‘lakli graf berilgan, bo‘laklari:
- chap: ,
- o‘ng: ,
Kun algoritmi — ikki ulushli (bipartite) grafda maksimal juftlashtirish
Ikki bo‘lakli graf berilgan, bo‘laklari:
Eng katta matching — umumiy uchlari bo‘lmagan qirralarning maksimal to‘plamini topish talab qilinadi.
Kun algoritmi — Berj teoremasining bevosita qo‘llanilishi:
Matching maksimal ⇔ grafda oshiruvchi zanjirlar yo‘q.
Algoritm shunday ishlaydi:
Oshiruvchi zanjir — yo‘l bo‘lib, u:
Zanjir bo‘ylab qirralarni almashtirgandan so‘ng matching o‘lchami 1 ga ortadi.
Chap bo‘lakdagi uchi uchun:
Ya’ni:
→ ni bilan bog‘laymiz
Barcha uchun:
Har bir DFS —
martagacha ishga tushiramiz:
Eng yomon holatda:
Muhim:
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";
}
}
}