leetcode 2316.统计无向图中无法互相到达点对数

思路：并查集

其实就是连通块的一个变形题目，一般的连通块题目要我们求的是连通个数，或者能不能到达，这里反过来问了。

首先，我们用dfs也是可以做到的，在dfs中统计每一个连通块的个数，然后用乘法原理相乘，累计相加就得到结果了。

这里并查集思路差不多，只是用了并查集来找连通块而已。（这里并查集多了一个权值，用来统计每个并查集的点的个数）

注意：作者在统计多少对点到达不了的时候不会统计。这里看题解给出了思路，就是对于每一个连通块来说，连通块里面的点和另一个连通块里面的点是互不联通的，所以这里可以用乘法原理相乘，接着，我们再加入累加器当中，然后让点的个数合并成这两个连通块一共的点数，再让下一个连通块乘以这些点数，因为下一个连通块的每一点又与这两个连通块的每一个点都不相通，所以继续这样下去，累加，计数....

上代码：

class Solution {
public:
int f[100020];
int zhi[100020];
int find(int u){
    if(f[u]==u)
    return u;
    else
    return f[u]=find(f[u]);
}
void unit(int x,int y){
    int s=find(x);
    if(find(y)==s)
    return;
    else
    {
        zhi[find(y)]+=zhi[s];
        f[s]=find(y);
        
    }
}
    long long countPairs(int n, vector<vector<int>>& edges) {
        for(int i=0;i<n;i++){
            f[i]=i;
            zhi[i]=1;
        }
        for(int i=0;i<edges.size();i++){
            int x=edges[i][0];
            int y=edges[i][1];
            unit(x,y);
        }
        long long res=0;
        long long size=0;
        for(int i=0;i<n;i++){
            if(f[i]==i){
                res+=zhi[i]*size;//
                size+=zhi[i];//需要学习的地方
            }
        }
        return res;
    }
};