做美食没有广告的网站,网站开发还有哪些,网站列表页内容,域名和网站思路#xff1a;并查集
其实就是连通块的一个变形题目#xff0c;一般的连通块题目要我们求的是连通个数#xff0c;或者能不能到达#xff0c;这里反过来问了。
首先#xff0c;我们用dfs也是可以做到的#xff0c;在dfs中统计每一个连通块的个数#xff0c;然后用乘…思路并查集
其实就是连通块的一个变形题目一般的连通块题目要我们求的是连通个数或者能不能到达这里反过来问了。
首先我们用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 sfind(x);if(find(y)s)return;else{zhi[find(y)]zhi[s];f[s]find(y);}
}long long countPairs(int n, vectorvectorint edges) {for(int i0;in;i){f[i]i;zhi[i]1;}for(int i0;iedges.size();i){int xedges[i][0];int yedges[i][1];unit(x,y);}long long res0;long long size0;for(int i0;in;i){if(f[i]i){reszhi[i]*size;//sizezhi[i];//需要学习的地方}}return res;}
};
