seo整站优化方案,网页设计制作个人简历代码,设计公司logo大全,闲置电脑做网站服务器这种涉及不同连通分量的#xff0c;看上去就可以用并查集。并查集的模板请参见上一篇内容。并查集#xff08;力扣1971#xff09;-CSDN博客
现在我们要求的是无法互相到达的点对。根据观察易得#xff0c;我们只需要求出每个并查集的元素数量#xff0c;然后遍历每个点看上去就可以用并查集。并查集的模板请参见上一篇内容。并查集力扣1971-CSDN博客
现在我们要求的是无法互相到达的点对。根据观察易得我们只需要求出每个并查集的元素数量然后遍历每个点设它所在的并查集元素数量为size那么它所不能到达的点的数量就为n-size.最后除2即可。
class Solution
{
public:int find(vectorint father, int u){return u father[u] ? u : father[u] find(father, father[u]);}void join(vectorint father, int u, int v){u find(father, u);v find(father, v);if (u v) return;father[v] u;}long long countPairs(int n, vectorvectorint edges){vectorintfather(n);for (int i 0; i n; i)//并查集初始化{father[i] i;}unordered_mapint, intmp;//mp.first:并查集的根值 mp.second:集合中元素的数量for (auto p : edges){join(father,p[0], p[1]);}for (int i 0; i n; i){int root find(father, i);//找到节点i的根值mp[root];//mp[root]以root为根的并查集的元素数量}long long ans 0;//查询每一个点看它所在的并查集中的元素的数量设为size则n-size是它不能访问到的节点的数量for (int i 0; i n; i){int root find(father, i);//找到它的根节点ans (n - mp[root]);}return ans / 2;}
};
