2316. Count Unreachable Pairs of Nodes

Question

You are given an integer n. There is an undirected graph with n nodes, numbered from 0 to n - 1. You are given a 2D integer array edges where edges[i] = [a<sub>i</sub>, b<sub>i</sub>] denotes that there exists an undirected edge connecting nodes a<sub>i</sub> and b<sub>i</sub>.

Return the number of pairs of different nodes that are unreachable from each other.

Solution

并查集，将所有元素union，然后计算每个元素所在集之外的元素和相加即可。
注意由于是无向图，因此计算加和时每两个点之间都计算了两次，因此需要将结果除以2。

路径压缩

在进行find()查找时，将经过的每一个节点设置为根节点。
这样做可以有效的降低树高，减少操作次数。
采用递归的形式实现。

按秩合并

用size[]数组记录当前位置的节点数量。
在合并两个数字时，将秩较小的数字指向秩较大的数字。
并更新根节点的size[]值。

Code

class Solution {
    public long countPairs(int n, int[][] edges) {
        UnionFind uf = new UnionFind(n);
        long res = 0;
        for(int[] edge : edges){
            uf.union(edge[0], edge[1]);
        }
        
        for(int i = 0; i < n; i++){
            res +=  ( n - uf.getSize(i) );
        }
        return res/2;   //无向图，因此每两个节点计算了两次
    }
    
    class UnionFind {
        int[] parent;
        int[] size;

        public UnionFind(int n){
            parent = new int[n];
            size = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        } 
           
        private int find(int id){
            return parent[id] == id ? id : find(parent[id]);   //路径压缩，将路径上的所有节点归结到根节点上
        }
           
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(size[p1] > size[p2]){    //按秩进行压缩
                parent[p2] = p1;
                size[p1] += size[p2];
            }
            else{
                parent[p1] = p2;
                size[p2] += size[p1];
            }
            return true;
        }

        public int getSize(int num){
            return size[find(num)];
        }
    }
}****