网站建设的技巧有哪些苏州seo公司排名

思路：并查集

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

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

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

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

上代码：

class Solution {
public:
int f[100020];
int zhi[100020];
int find(int u){if(f[u]==u)return u;elsereturn 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;}
};