并查集

class UF {
// 记录连通分量
private int count
// 节点x的父节点是parent[x]
private int[] parent;
// 新增一个数组来记录树的“重量” 为了避免造成树的不平衡
private int[] size;

/*构造函数， n为图的节点总数*/
public UF(int n) {
    // 一开始互不相通
    this.count = n; // 连通分量的个数    
    // 父节点指针指向自己
    parent = new int[n];
    // 最初每棵树只有一个节点
    // 重量应该初始化为1
    size = new int[n];
    for (int i=0; i<n; i++) {
        parent[i] = i;
        size[i] = 1;  // 初始状态的节点个数为1
    }
}

/* 将p和q连接 */
public void union(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    if (rootP == rootQ) 
        return;
    // 将两棵树合并为一颗
    // 小树接到大树下面，较平衡
    if (size[rootP] > size[rootQ]) {
        parent[rootQ] = rootP;
        size[rootP] += size[rootQ];
    } else {
        parent[rootP] = rootQ;
        size[rootQ] += rootP; 
    }
    count--; // 两个分量合二为一 
}

/* 返回某个节点x的根节点 */
private int find(int x) {
    // 根节点parent[x] == x
    while (parent[x] != x) {
        // 进行路径压缩
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

/* 判断p和q是否连通*/
public boolean connected(int p, int q) {
    int rootP = find(p);
    int rootQ = find(q);
    return rootP == rootQ;
}

/* 返回图中有多少个联通分量 */
public int count() {
    return count;
}

}