POJ 1308 Is It A Tree?：並查集判斷有向樹

POJ 1308 Is It A Tree?：並查集判斷有向樹

給定有向邊序列，判斷是否構成一棵樹。樹的定義：有且僅有一個根（入度 0）、其餘節點入度為 1、無環、連通。

判斷條件總結

1. 空圖是樹：無邊輸入 (0 0) 直接判定為樹
2. 無自環：u → u 直接判非樹
3. 入度條件：恰好一個節點入度 0（根），其餘入度 1
4. 無環連通：並查集檢測環 + 最終連通分量數 = 1

並查集解法流程

1. 讀入邊 (u, v)，u→v
2. 若 u==v：標記非樹
3. 記錄所有出現的節點，離散化映射到 0..n-1
4. 並查集 unite(u, v)，若 find(u)==find(v) 則有環
5. 統計入度，檢查入度條件
6. 檢查連通性：所有節點 find 後唯一根

C++ 參考實現

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

struct UnionFind {
    vector<int> p, r;
    UnionFind(int n) : p(n), r(n, 0) { iota(p.begin(), p.end(), 0); }
    int find(int x) { return p[x] == x ? x : p[x] = find(p[x]); }
    bool unite(int a, int b) {
        a = find(a); b = find(b);
        if (a == b) return false;
        if (r[a] < r[b]) swap(a, b);
        p[b] = a;
        if (r[a] == r[b]) r[a]++;
        return true;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int u, v, case_no = 1;
    while (cin >> u >> v) {
        if (u == -1 && v == -1) break;
        
        vector<pair<int,int>> edges;
        set<int> nodes;
        bool is_tree = true;
        
        if (u == 0 && v == 0) { // 空樹
            cout << "Case " << case_no++ << " is a tree.\n";
            continue;
        }
        
        edges.emplace_back(u, v);
        nodes.insert(u); nodes.insert(v);
        if (u == v) is_tree = false;
        
        while (cin >> u >> v) {
            if (u == 0 && v == 0) break;
            edges.emplace_back(u, v);
            nodes.insert(u); nodes.insert(v);
            if (u == v) is_tree = false;
        }
        
        if (!is_tree) {
            cout << "Case " << case_no++ << " is not a tree.\n";
            continue;
        }
        
        // 離散化
        unordered_map<int,int> id;
        int idx = 0;
        for (int x : nodes) id[x] = idx++;
        
        UnionFind uf(idx);
        vector<int> in_deg(idx, 0);
        
        for (auto [a, b] : edges) {
            int u = id[a], v = id[b];
            if (!uf.unite(u, v)) { is_tree = false; break; }
            in_deg[v]++;
        }
        
        if (!is_tree) {
            cout << "Case " << case_no++ << " is not a tree.\n";
            continue;
        }
        
        // 檢查入度：恰好一個 0，其餘 1
        int root_count = 0;
        for (int d : in_deg) {
            if (d == 0) root_count++;
            else if (d > 1) { is_tree = false; break; }
        }
        if (root_count != 1) is_tree = false;
        
        // 檢查連通性
        int root = uf.find(0);
        for (int i = 1; i < idx; ++i)
            if (uf.find(i) != root) { is_tree = false; break; }
        
        cout << "Case " << case_no++ << (is_tree ? " is a tree." : " is not a tree.") << "\n";
    }
    return 0;
}

關鍵細節

複雜度

• 時間：O(E α(V))，極快
• 空間：O(V + E)

替代方案：拓撲排序

也可用 Kahn 算法：入度為 0 的節點入隊，拓撲排序成功且處理節點數 = 總節點數 ⇒ 是樹。但並查集更直觀易實現。

此題是並查集判斷有向圖是否為樹的模板題，綜合考察入度統計、環檢測、連通性三大核心條件。