BZOJ 1116 CLO：並查集判斷圖匹配

問題描述

給定一個無向圖，問是否存在一個點與邊的匹配，使得匹配數等於點數（即每個點恰好匹配一條邊，每條邊至多匹配一個點）。

解題思路

這等價於判斷圖中每個連通分量的邊數是否 ≥ 點數。因為在一個連通分量中，若邊數 < 點數，則為樹或森林，無法完美匹配所有點；若邊數 ≥ 點數，則至少存在一個環，可以構造匹配。使用並查集維護每個連通分量的點數和邊數，最後檢查每個分量是否 edgeCnt >= nodeCnt。

代碼實現 (C++)

#include 
using namespace std;
const int MAXN = 100100;
int fa[MAXN], nodeCnt[MAXN], edgeCnt[MAXN];
bool hasCycle[MAXN];

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

void unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) {
        edgeCnt[x]++;
        hasCycle[x] = true;
        return;
    }
    fa[x] = y;
    nodeCnt[y] += nodeCnt[x];
    edgeCnt[y] += edgeCnt[x] + 1;
    hasCycle[y] = hasCycle[y] || hasCycle[x];
}

int main() {
    int n, m; cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fa[i] = i;
        nodeCnt[i] = 1;
        edgeCnt[i] = 0;
        hasCycle[i] = false;
    }
    for (int i = 0; i < m; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        unite(u, v);
    }
    bool ok = true;
    for (int i = 1; i <= n; ++i) if (find(i) == i) {
        if (edgeCnt[i] < nodeCnt[i]) { ok = false; break; }
    }
    cout << (ok ? "TAK" : "NIE") << endl;
    return 0;
}

複雜度分析

• 時間複雜度：O((n+m) α(n))，近似線性。
• 空間複雜度：O(n)。

總結

本題將圖匹配問題轉化為連通分量邊點數關係，並查集完美支持動態合併與統計。注意合併同一分量內的邊會形成環，需單獨計數。