并查集：从连通性检测到动态合并的算法艺术

并查集：从连通性检测到动态合并的算法艺术（C++实现）

一、并查集：算法世界的隐形支柱

在算法竞赛和工程实践中，并查集（Disjoint Set Union，DSU）是解决动态连通性问题的终极武器。它能在近乎常数时间内完成集合的合并与查询操作，广泛应用于社交网络、图像处理、编译器优化等领域。本文将深入剖析并查集的核心原理，并通过实战案例揭示其精妙之处。

二、并查集的三重核心

1. 数据结构设计

class DSU {
    vector<int> parent;
    vector<int> rank; // 按秩合并优化
public:
    DSU(int n) : parent(n), rank(n, 1) {
        iota(parent.begin(), parent.end(), 0); // 初始化每个元素为独立集合
    }
    
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]); // 路径压缩
    }
    
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        
        // 按秩合并
        if(rank[x] < rank[y]) swap(x, y);
        parent[y] = x;
        rank[x] += rank[y];
    }
};

2. 时间复杂度分析

其中，α(n) 是反阿克曼函数，增长极其缓慢，可视为常数。

三、五大经典应用场景

场景1：朋友圈问题（LeetCode 547）

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    DSU dsu(n);
    
    for(int i=0; i<n; ++i) {
        for(int j=i+1; j<n; ++j) {
            if(isConnected[i][j]) {
                dsu.unite(i, j);
            }
        }
    }
    
    unordered_set<int> unique;
    for(int i=0; i<n; ++i) {
        unique.insert(dsu.find(i));
    }
    return unique.size();
}

场景2：最小生成树（Kruskal算法）

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    int totalWeight = 0;
    
    for(const auto& e : edges) {
        if(dsu.find(e.u) != dsu.find(e.v)) {
            dsu.unite(e.u, e.v);
            totalWeight += e.weight;
        }
    }
    return totalWeight;
}

四、四大优化策略

策略1：路径压缩

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

策略2：按秩合并

void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    
    if(rank[x] < rank[y]) swap(x, y);
    parent[y] = x;
    rank[x] += rank[y];
}

策略3：启发式合并

void unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return;
    
    if(size[x] < size[y]) swap(x, y);
    parent[y] = x;
    size[x] += size[y];
}

策略4：持久化并查集

struct PersistentDSU {
    vector<int> parent, time;
    vector<vector<pair<int, int>>> history;
    
    int find(int x, int t) {
        while(parent[x] != x && time[x] <= t) {
            x = parent[x];
        }
        return x;
    }
};

五、性能天梯图（n=1e6操作）

六、三大扩展问题

问题1：带权并查集

class WeightedDSU {
    vector<int> parent;
    vector<int> weight; // 到父节点的权重
    
    pair<int, int> find(int x) {
        if(parent[x] != x) {
            auto [root, w] = find(parent[x]);
            parent[x] = root;
            weight[x] += w;
        }
        return {parent[x], weight[x]};
    }
};

问题2：动态连通性

class DynamicDSU {
    vector<int> parent;
    vector<set<int>> children;
    
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        
        if(children[x].size() < children[y].size()) swap(x, y);
        parent[y] = x;
        children[x].insert(children[y].begin(), children[y].end());
    }
};

问题3：可撤销操作

class RollbackDSU {
    vector<int> parent;
    vector<pair<int, int>> history;
    
    int find(int x) {
        while(parent[x] != x) x = parent[x];
        return x;
    }
    
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if(x == y) return;
        
        history.emplace_back(x, parent[x]);
        parent[x] = y;
    }
    
    void rollback() {
        auto [x, p] = history.back();
        history.pop_back();
        parent[x] = p;
    }
};

七、常见陷阱与规避

陷阱1：未初始化

// 错误写法
DSU dsu;
dsu.find(0);

// 正确写法
DSU dsu(n);

陷阱2：路径压缩破坏权重

// 错误写法
int find(int x) {
    if(parent[x] != x) {
        parent[x] = find(parent[x]);
        weight[x] += weight[parent[x]]; // 错误！
    }
    return parent[x];
}

// 正确写法
pair<int, int> find(int x) {
    if(parent[x] != x) {
        auto [root, w] = find(parent[x]);
        parent[x] = root;
        weight[x] += w;
    }
    return {parent[x], weight[x]};
}

八、实战训练场

1. LeetCode 684：冗余连接
2. LeetCode 128：最长连续序列
3. Codeforces 25D：道路修复
4. POJ 1182：食物链（带权并查集）

并查集不仅是算法工具箱中的利器，更是一种动态维护集合关系的思维方式。掌握其核心优化技巧和扩展应用，可以让你在算法竞赛和工程实践中游刃有余。记住：每个 find 操作都是一次路径优化，每次 unite 都是一次集合进化！