leetcode2022年度刷题分类型总结（十二）并查集

并查集模板如下：

int n = 1005; // 节点数量3 到 1000
int father[1005];

// 并查集初始化
void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}
// 并查集里寻根的过程
int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]);
}
// 将v->u 这条边加入并查集
void join(int u, int v) {
    u = find(u);
    v = find(v);
    if (u == v) return ;
    father[v] = u; //一般靠左原则，即让左边变成右边的爹（，原则靠左靠右均可，因为题目一般只会问谁和谁一组，或者一共几个组，组长是谁没个定数，除非题目特殊要求）
}
// 判断 u 和 v是否找到同一个根
bool same(int u, int v) {
    u = find(u);
    v = find(v);
    return u == v;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

以上模板汇总，只要修改 n 和father数组的大小就可以了。

并查集主要有三个功能。

1. 寻找根节点，函数：find(int u)，也就是判断这个节点的祖先节点是哪个
2. 将两个节点接入到同一个集合，函数：join(int u, int v)，将两个节点连在同一个根节点上
3. 判断两个节点是否在同一个集合，函数：same(int u, int v)，就是判断两个节点是不是同一个根节点

模板来源：代码随想录

例一：擒贼先擒王

一共有10个强盗，编号1-10，已知：同伙关系有：
【1，2】、【3，4】、【5，2】、【4，6】、【2，6】、【8，7】、【9，7】、【1，6】、【2，4】
强盗的同伙也是同伙，求：查出有多少个独立的犯罪集团

#include<stdio.h>
int f[1000]={0},n,m,k,sum=0;
//int total=100000;
void init(){
    int i;
    for(i=1;i<=n;i++){
        f[i]=i;
    }
    return;
}

int getf(int v){
    if(f[v]==v)
        return v;
    else{
        f[v]=getf(f[v]);
        return f[v]
        //这里是路径压缩，每次函数返回时，顺路把路上遇到人的boss改为最终找到的祖宗编号
        //这样可以提高找到最终祖先的速度
    }
}
void merge(int v,int u){
    int t1,t2;//t1,t2分别int v,int u的大boss，每次双方会谈都是最高领导人
    t1=getf(v);
    t2=getf(u);
    if(t1!=t2){//判断两结点是否同一集合
        f[t2]=t1;//“靠左” 原则，左边变成右边的boss
        //经过路径压缩，把
        
    }
    
}

int main(){
    int i,x,y;
    scanf("%d",&n); //n个人
    scanf("%d",&m);//

    init(); //初始化
    for(i=1;i<=m;i++){ //数据录入
        scanf("%d %d",&x,&y);
        merge(x,y) //合并
        }
    
    for(i=1;i<=n;i++){ //找到各个大boss
        if(f[i]==i){
            sum++;
        }
    }
    printf("%d\n",sum);//最后一共有多少个独立的犯罪团伙
    getchar();getchar();
    return 0

    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

例二：朋友圈

示例1
输入
2
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
输出
4
2

#include<bits/stdc++.h>
using namespace std;
 
unordered_map<int, int>fa;
unordered_map<int, int>cnt;
 
int find(int x){
    if(fa.find(x)==fa.end()){
        fa[x]=x;
        cnt[x]=0;
    }
    if(x==fa[x]){
        return x;
    }
    return fa[x]=find(fa[x]);
}
void Union(int x,int y){
    int fx=find(x);
    int fy=find(y);
    fa[fx]=fy;
}
int main(){
    int T;cin>>T;
    while(T-- >0){
        int n;cin>>n;
        while(n-- >0){
            int x,y;
            cin>>x>>y;
            Union(x,y);
        }
        int ans=0;
        for(unordered_map<int, int>::iterator it=fa.begin();it!=fa.end();it++){
            int fi=find(it->second);
            cnt[fi]++;
            ans=max(ans,cnt[fi]);
        }
        cout<<ans<<endl;
        fa.clear();
        cnt.clear();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

例三：684. 冗余连接

树可以看成是一个连通且 无环 的 无向 图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

class Solution {
private:
    int n=1005;
    int father[1005];
    void init(){
        for(int i=0;i<n;i++){
            father[i]=i;
        }
    }
    int find(int u){
        if(father[u]==u){
            return u;
        }
        return father[u]=find(father[u]);
    }
    void join(int u,int v){
        u=find(u);
        v=find(v);
        if(u==v) return;
        father[v]=u;
    }
    bool same(int u,int v){
        u=find(u);
        v=find(v);
        return u==v;
    }
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        // 思路是从前向后遍历每一条边，边的两个节点如果不在同一个集合，就加入集合（即：同一个根节点）。
        //如果边的两个节点已经出现在同一个集合里，说明边的两个节点已经连在一起了，如果再加入这条边一定就出现环了。
        init();
        vector<int> ans;
        for(int i=0;i<edges.size();i++){
            if(same(edges[i][0],edges[i][1])){
                ans=edges[i];
                break;
            }
            join(edges[i][0],edges[i][1]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42