一、并查集的理解

算法学习笔记(1) : 并查集

二、并查集模板

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

优化后的find 路径压缩

int find(int x)
{
    if(x == fa[x])
        return x;
    else{
        fa[x] = find(fa[x]);  //父节点设为根节点
        return fa[x];         //返回父节点
    }
}

三、题目总结

比较简单点的
547 省份数量
1319 连通网络的操作次数
990 等式方程的可满足性
684 冗余连接