【力扣刷题】2316. 统计无向图中无法互相到达点对数-并查集

给你一个整数 n ，表示一张 无向图 中有 n 个节点，编号为 0 到 n - 1 。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

请你返回 无法互相到达 的不同 点对数目 。

示例 1：

输入：n = 3, edges = [[0,1],[0,2],[1,2]]
输出：0
解释：所有点都能互相到达，意味着没有点对无法互相到达，所以我们返回 0 。
1
2
3
示例 2：

输入：n = 7, edges = [[0,2],[0,5],[2,4],[1,6],[5,4]]
输出：14
解释：总共有 14 个点对互相无法到达：
[[0,1],[0,3],[0,6],[1,2],[1,3],[1,4],[1,5],[2,3],[2,6],[3,4],[3,5],[3,6],[4,6],[5,6]]
所以我们返回 14 。
1
2
3
4
5
提示：

1 <= n <= 105
0 <= edges.length <= 2 * 105
edges[i].length == 2
0 <= ai, bi < n
ai != bi
不会有重复边。
// 方法一：乘法原理+Solution类内函数
class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
vector<int> f(n);
for(int i=0;i<n;i++){
f[i]=i;
}
// 匿名函数构造方法
function<int(int)>find = [&](int x) -> int{
if(f[x]==x){
return x;
}
return f[x]=find(f[x]);
};
function<void(int,int)>unione = [&](int a,int b) -> void{
f[find(a)]=find(b);
};
for(auto &e:edges){
unione(e[0],e[1]);
}
unordered_map<int,int>m;
for(int i=0;i<n;i++){
m[find(i)]++;
}
// total代表已遍历的连通块的总点的个数
long long ans=0,total=0;
for(auto [_,x]:m){
ans+=total*x;
total+=x;
}
return ans;
}
};

//方法二：“总量-连通分量”+UnionFind类
class UnionFind{
private:
vector<int>f,size;
public:
UnionFind(int n):f(n),size(n,1){
iota(f.begin(),f.end(),0);
}
int Find(int x){
if(f[x]==x){
return x;
}
return f[x]=Find(f[x]);
}
void Unione(int a,int b){
int aa=Find(a),bb=Find(b);
if(aa!=bb){
//路径压缩
if(size[aa]>size[bb]){
size[aa]+=size[bb];
f[bb]=aa;
}else{
size[bb]+=size[aa];
f[aa]=bb;
}
}
}
int GetSize(int x){
return size[x];
}
};
class Solution {
public:
long long countPairs(int n, vector<vector<int>>& edges) {
UnionFind uf(n);
for(auto &e:edges){
uf.Unione(e[0],e[1]);
}
long long ans=0;
for(int i=0;i<n;i++){
ans+=n-uf.GetSize(uf.Find(i));
}
return ans/2;
}
};

/*
今日总结：
1. function<输出类型(输入类型)> 名称 = [&](输入变量) -> 输出类型{ }
2.
加法原理
做一件事，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N=m1+m2+m3+…+mn种不同方法。每一种方法都能够直接达成目标。
乘法原理
做一件事，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事共有N=m1×m2×m3×…×mn种不同的方法。
3.还可以使用dfs
4.iota(f.begin(),f.end(),0);填充0于这段范围
*/