Hopcroft-Karp

Hopcroft-Karp là thuật toán tìm cặp ghép cực đại trên đồ thị hai phía (maximum bipartite matching) trong $O(E\sqrt{V})$, nhanh hơn hẳn cách ghép tham lam bằng đường tăng (augmenting path) tuần tự kiểu Kuhn/Hungarian chạy $O(VE)$. Với đồ thị dày ($V$ tới ${10}^4$–${10}^5$, $E$ lớn), thừa số $\sqrt{V}$ thay cho $V$ tạo khác biệt sống còn giữa AC và TLE.

Bài toán: cho đồ thị hai phía với tập trái $L$ và tập phải $R$, mỗi cạnh nối một đỉnh trái với một đỉnh phải. Một cặp ghép (matching) là tập cạnh đôi một không chung đỉnh. Ta muốn chọn nhiều cạnh nhất.

Ý tưởng / Trực giác

Mọi thuật toán ghép cặp đều dựa trên đường tăng (augmenting path): một đường đi xen kẽ cạnh-chưa-ghép / cạnh-đã-ghép, bắt đầu và kết thúc ở hai đỉnh chưa ghép. Nếu lật trạng thái mọi cạnh dọc đường này (cạnh chưa ghép → ghép, cạnh ghép → chưa ghép), số cạnh ghép tăng đúng 1. Định lý Berge: một cặp ghép là cực đại khi và chỉ khi không còn đường tăng nào.

Thuật toán Kuhn tìm từng đường tăng một, mỗi lần một DFS $O(E)$, cần tối đa $V$ lần → $O(VE)$.

Hopcroft-Karp tăng tốc nhờ một quan sát then chốt:

1. Tìm cả một "tập" đường tăng ngắn nhất cùng lúc. Mỗi pha gồm hai bước:

   • BFS phân tầng: xuất phát đồng thời từ tất cả đỉnh trái chưa ghép, gán "khoảng cách" (số tầng) cho từng đỉnh trái, dừng khi chạm tới một đỉnh phải chưa ghép. BFS tìm ra độ dài đường tăng ngắn nhất hiện tại.
   • DFS theo tầng: tìm một tập tối đại các đường tăng ngắn nhất rời đỉnh nhau rồi augment tất cả trong cùng một lượt.

2. Vì sao chỉ cần $O(\sqrt{V})$ pha? Có hai lập luận ghép lại:

   • Sau mỗi pha, độ dài đường tăng ngắn nhất tăng nghiêm ngặt (giống Dinic). Nên sau $\sqrt{V}$ pha đầu, mọi đường tăng còn lại đều dài $\ge \sqrt{V}$.
   • Các đường tăng còn thiếu rời đỉnh nhau; nếu cặp ghép tối ưu còn hơn cặp hiện tại $k$ cạnh thì có $k$ đường tăng rời nhau. Mỗi đường dài $\ge \sqrt{V}$ chiếm $\ge \sqrt{V}$ đỉnh, mà chỉ có $V$ đỉnh, nên $k\le \sqrt{V}$. Mỗi pha tăng ít nhất 1 cặp, nên còn tối đa $\sqrt{V}$ pha nữa.

   Tổng: $O(\sqrt{V})$ pha, mỗi pha một BFS + một loạt DFS tốn $O(E)$ → $O(E\sqrt{V})$.

Trực giác ngắn gọn: augment nhiều đường ngắn song song trong mỗi pha thay vì một đường mỗi lần, hệt như Dinic so với Ford-Fulkerson — và thực chất Hopcroft-Karp chính là Dinic áp dụng cho mạng đơn vị của bài ghép cặp hai phía.

Ví dụ chạy tay

Đồ thị hai phía: trái $L=\{1,2,3\}$, phải $R=\{a,b,c\}$ với các cạnh:

  L          R
  1 ───────── a
  1 ───────── b
  2 ───────── a
  3 ───────── b
  3 ───────── c

Danh sách kề: adj[1]={a,b}, adj[2]={a}, adj[3]={b,c}.

Khởi tạo: tất cả chưa ghép. match_l = match_r = -1.

Pha 1. BFS từ mọi đỉnh trái chưa ghép {1,2,3}, gán tầng dist:

dist_l:  1→0   2→0   3→0      (tất cả ở tầng 0, đều chưa ghép)
BFS chạm a (chưa ghép) và b (chưa ghép) ⇒ found = true, đường tăng ngắn nhất dài 1

DFS lần lượt các đỉnh trái chưa ghép, mỗi DFS tìm 1 đường tăng rời đỉnh:

dfs(1): a chưa ghép  ⇒ ghép 1–a            matching=1
dfs(2): a đã bị 1 chiếm, match_r[a]=1; thử đi tiếp nhưng a là đỉnh phải đã ghép,
        cạnh duy nhất của 2 là a ⇒ thất bại                (2 chưa ghép)
dfs(3): b chưa ghép  ⇒ ghép 3–b            matching=2

Trạng thái sau pha 1:

  1 ═══════ a        (═ là cạnh đã ghép)
  3 ═══════ b
  2, c  chưa ghép

Pha 2. BFS từ đỉnh trái chưa ghép còn lại = {2}:

dist_l[2]=0
  từ 2 → a, match_r[a]=1 ⇒ đi tiếp lên đỉnh trái 1: dist_l[1]=1, đẩy 1 vào hàng đợi
  từ 1 → b, match_r[b]=3 ⇒ đi tiếp lên đỉnh trái 3: dist_l[3]=2, đẩy 3 vào hàng đợi
  từ 3 → c, match_r[c]=-1 (chưa ghép) ⇒ found = true

Tầng tìm được:

dist_l:  2→0   1→1   3→2
đường tăng ngắn nhất:  2 →a→ 1 →b→ 3 →c   (dài 5, lật trạng thái 3 cạnh)

DFS(2) đi theo điều kiện dist_l[w] == dist_l[u]+1:

2 → a (match=1), dfs(1): 1 → b (match=3), dfs(3): 3 → c (chưa ghép) ✓
lật dọc đường:  ghép 2–a, 1–b, 3–c

Trạng thái cuối:

  2 ═══════ a
  1 ═══════ b
  3 ═══════ c        matching = 3

Pha 3. BFS không còn đỉnh trái chưa ghép ⇒ found = false ⇒ dừng. Kết quả: cặp ghép cực đại bằng 3 (ghép hoàn hảo). Toàn bộ chỉ tốn 2 pha thực sự augment.

Cài đặt

Quy ước: đỉnh trái đánh số $1..n\_left$, đỉnh phải $1..n\_right$. match_l[u] = đỉnh phải đang ghép với $u$ (hoặc $-1$); match_r[v] tương tự cho đỉnh phải. dist_l[u] là số tầng BFS của đỉnh trái $u$.

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;
const int MAXN = 2e5 + 5;

int n_left, n_right;
vector<int> adj[MAXN];   // adj[u] = các đỉnh phải kề với đỉnh trái u

int match_l[MAXN], match_r[MAXN];  // bạn ghép hiện tại (-1 nếu chưa ghép)
int dist_l[MAXN];                  // tầng BFS của đỉnh trái

// BFS phân tầng: tìm độ dài đường tăng ngắn nhất, gán dist cho các đỉnh trái.
// Trả về true nếu còn ít nhất một đường tăng.
bool bfs() {
    queue<int> q;
    for (int u = 1; u <= n_left; u++) {
        if (match_l[u] == -1) { dist_l[u] = 0; q.push(u); } // nguồn = đỉnh trái chưa ghép
        else dist_l[u] = INF;
    }
    bool found = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            int w = match_r[v];        // đỉnh trái đang ghép với v (qua cạnh ngược)
            if (w == -1) found = true; // chạm đỉnh phải chưa ghép ⇒ có đường tăng
            else if (dist_l[w] == INF) {   // đỉnh trái w chưa được phân tầng
                dist_l[w] = dist_l[u] + 1;
                q.push(w);
            }
        }
    }
    return found;
}

// DFS theo tầng: thử dựng một đường tăng ngắn nhất xuất phát từ u.
bool dfs(int u) {
    for (int v : adj[u]) {
        int w = match_r[v];
        // hoặc v chưa ghép (kết thúc đường tăng), hoặc đi tiếp đúng tầng kế tiếp
        if (w == -1 || (dist_l[w] == dist_l[u] + 1 && dfs(w))) {
            match_l[u] = v;            // lật trạng thái: ghép u–v
            match_r[v] = u;
            return true;
        }
    }
    dist_l[u] = INF; // đánh dấu u đã hỏng trong pha này để khỏi thử lại
    return false;
}

int hopcroft_karp() {
    fill(match_l + 1, match_l + n_left + 1, -1);
    fill(match_r + 1, match_r + n_right + 1, -1);
    int matching = 0;
    while (bfs()) {                    // mỗi vòng = một pha
        for (int u = 1; u <= n_left; u++)
            if (match_l[u] == -1 && dfs(u)) matching++;
    }
    return matching;
}

Cách dùng: đọc đồ thị, đẩy cạnh vào adj, gọi hopcroft_karp(). Để truy vết cặp ghép, đọc lại mảng match_l/match_r sau khi chạy.

Độ phức tạp

• Thời gian: $O(E\sqrt{V})$. Có $O(\sqrt{V})$ pha (chứng minh ở mục Trực giác: sau $\sqrt{V}$ pha, đường tăng còn lại dài $\ge \sqrt{V}$, mà các đường rời đỉnh nhau nên còn $\le \sqrt{V}$ cái). Mỗi pha gồm một BFS quét toàn bộ cạnh $O(E)$ và một loạt DFS mà tổng chi phí cũng $O(E)$ (nhờ dòng dist_l[u] = INF đánh dấu đỉnh hỏng, mỗi cạnh được DFS xét $O(1)$ lần trong một pha). Tổng $O(\sqrt{V}·E)$.
• Bộ nhớ: $O(V+E)$. Danh sách kề adj chứa $E$ phần tử; các mảng match_l, match_r, dist_l cùng hàng đợi BFS đều $O(V)$. Lưu ý đệ quy của dfs có thể sâu tới $O(V)$ — với $V$ lớn nên cân nhắc khử đệ quy hoặc tăng kích thước stack.

So sánh:

Với $V~{10}^5,E~{10}^6$: Kuhn $~{10}^{11}$ (TLE), Hopcroft-Karp $~3\times {10}^8$ (vừa sức).

⚠️ Lỗi thường gặp

• Đánh số đỉnh trái và phải trùng miền. match_l index theo đỉnh trái, match_r index theo đỉnh phải — phải là hai mảng riêng, đánh số độc lập từ 1. Nếu gộp chung một không gian chỉ số sẽ ghi đè lẫn nhau. Triệu chứng: kết quả nhỏ hơn thực tế hoặc sai loạn.
• Quên dòng dist_l[u] = INF cuối hàm dfs. Đây là tối ưu sống còn: nó đánh dấu đỉnh đã thất bại trong pha hiện tại để DFS sau không thử lại. Bỏ nó đi thì mỗi pha không còn là $O(E)$ mà có thể bùng nổ thành mũ — không sai kết quả nhưng TLE.
• Điều kiện đi tiếp trong DFS sai. Phải là dist_l[w] == dist_l[u] + 1 (đúng một tầng kế tiếp). Nếu viết >= hay quên kiểm tra tầng, DFS đi lung tung, không còn theo đường tăng ngắn nhất ⇒ mất tính đúng của số pha (và có thể lặp vô tận / sai kết quả).
• Vòng lặp pha sai vị trí if (match_l[u] == -1). Trong vòng for augment phải chỉ gọi dfs(u) với đỉnh trái đang chưa ghép; gọi cho đỉnh đã ghép sẽ lật hỏng cặp đã có.
• Kích thước mảng / số đỉnh. MAXN phải đủ cho max(n_left, n_right). Đồ thị có thể có $n\_left\ne n\_right$; cấp phát và fill theo đúng từng phía, đừng dùng chung một biến $n$.
• Stack overflow do đệ quy dfs sâu. Với chuỗi đường tăng dài, độ sâu đệ quy lên tới $O(V)$. Khi $V~{10}^5$ trở lên, hãy nới stack (ví dụ chạy luồng riêng đặt stack lớn) hoặc viết DFS lặp.
• Nhầm với ghép cặp có trọng số. Hopcroft-Karp chỉ giải ghép cặp cực đại không trọng số. Bài "tổng chi phí nhỏ nhất" (assignment problem) cần Hungarian / MCMF, không dùng được trực tiếp.

Biến thể / Mở rộng

• Định lý König: trên đồ thị hai phía, kích thước cặp ghép cực đại = kích thước phủ đỉnh nhỏ nhất (minimum vertex cover). Từ cặp ghép cực đại dựng được phủ đỉnh và tập độc lập lớn nhất (maximum independent set = $V$ − matching).
• Ghép cặp hai phía có trọng số (assignment / minimum cost perfect matching): dùng thuật toán Hungarian hoặc Min-Cost Max-Flow (MCMF), không phải Hopcroft-Karp.
• Quan hệ với luồng cực đại: Hopcroft-Karp chính là Dinic trên mạng đơn vị (unit-capacity) dựng từ đồ thị hai phía — đó là lý do nó đạt cùng cận $O(E\sqrt{V})$.
• Ghép cặp trên đồ thị tổng quát (không hai phía): cần thuật toán Blossom của Edmonds.

Bài tập luyện

• Ghép Cặp Tương Thích (compair) — (Trung cấp) Ghép cặp tối đa giữa các nhóm ID khi tổng bằng $A$ hoặc $B$ — mô hình hóa thành ghép cặp hai phía / luồng và rèn phản xạ "đây là bài matching".
• Bài Toán Phân Công (assgn) — (Kỳ cựu) Phân công $n$ công nhân cho $n$ việc với tổng chi phí nhỏ nhất: biến thể có trọng số của ghép cặp hai phía, giúp phân biệt rõ khi nào Hopcroft-Karp đủ, khi nào phải dùng Hungarian/MCMF.
• Ghép Đôi - Platinum (pairedup21) — (Chuyên gia) Ghép cặp cực đại Holstein–Guernsey theo ràng buộc khoảng cách, tối ưu tổng trọng số đỉnh không ghép — bài khó tổng hợp tư duy ghép cặp với cấu trúc bài toán thực tế.