数据结构

并查集

Posted by Liao on 2019-08-28

一. 定义

并查集 (Disjoint set) 是一种树型数据结构，用于处理一些不相交集合的合并及查询问题，或者检查图上是否存在环。

  • Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union：将两个子集合并成同一个集合。

性质：同一个集合的任意两个顶点相连会形成环

二. 分析

int find(int x):通过递归查找元素所在的根节点。

void union(int x,int y): 找到两个元素的根，并把其中一个元素（如x）的根节点设置为另一个元素（如y）的根节点，使得x所在的集合和y所在的集合合并。简单来说，就是让两个元素合并到相同的根。

模板

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
class UnionFind {
public:
    vector<int>parent;
    UnionFind(int n) {
        parent.resize(n);
        for(int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find_root(int x) {
        while(parent[x] != x) {
            parent[x] = find_root(parent[x]);
            x = parent[x];
        }
        return x;
    }
    
    bool isConnect(int x, int y) {
        return find_root(x) == find_root(y);
    }
    
    void union_vertices(int x, int y) { // 连接两个结点
        int x_root = find_root(x);
        int y_root = find_root(y);
        if(x_root != y_root) {
            parent[x_root] = y_root;
        }
    }

};

三. 题目

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
56
57
58
59
60
61
62
63
64
65
66
67
#include <stdio.h>
#include <iostream>
using namespace std;
const int maxn = 1050;
int s[maxn];
int height[maxn];
void init_set()  //初始化
{
    for(int i=1;i<=maxn;i++)
    {
         s[i] = i;
        height[i] = 0;
    }

}

int find_set(int x)  //寻根
{
    return x==s[x]?x:find_set(s[x]);
}

void union_set(int x,int y)  //合并
{
    x = find_set(x);
    y = find_set(y);
    if(height[x] == height[y])  //路径压缩  
    {
         height[x] = height[y]+1;
         s[y] = x;
    }
    else
    {
        if(height[x]<height[y])
        {
            s[x] = y;
        }
        else
            s[y] = x;
    }

}
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        int x,y;
        cin >> n >>m;
        init_set();
        for(int i=1;i<=m;i++)
        {
            cin >> x >> y;
            union_set(x,y);
        }
        int ans = 0;
        for(int i =1;i<=n;i++)
        {
            if(s[i] == i)
                ans++;
        }
        cout <<ans <<endl;
    }
    return 0;
}

HDU1856

2

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
56
57
58
59
60
61
62
63
64
#include <iostream>
#include<cstdio>
using namespace std;
const int maxn = 1e7+7;
int par[maxn],sum[maxn];
void init_set()
{
    for(int i=0;i<=1e7;i++)
    {
        par[i] = i;
        sum[i] = 0;
    }
}

int find_set(int x)
{
    while(x!=par[x])
        x = par[x];
    return x;
}

void Union(int x,int y)
{
    int fx = find_set(x);
    int fy = find_set(y);
    par[fy] = fx;
    int t;
    while(x!=fx)   //路径压缩
    {
        t = par[x];
        par[x] = fx;
        x = t;
    }
}
int main()
{
    int n;
    int x,y;
    while(scanf("%d",&n)!=EOF)
    {
        init_set();

        int Maxn = 0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d %d",&x,&y);
            if(x>Maxn)
                Maxn = x;
            if(y>Maxn)
                Maxn = y;
            if(find_set(x)!=find_set(y))
                Union(x,y);
        }
        int mmax = 1;
        for(int i=1;i<=Maxn;i++)
            sum[find_set(i)]++;
        for(int i=1;i<=Maxn;i++)
        {
            if(mmax<sum[i])
                mmax = sum[i];
        }
       printf("%d\n",mmax);
    }
}

POJ2524

输入n,m,分别表示学生个数和一共多少行，输出最多有多少不同的宗教信仰。

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
#include <iostream>
#include<cstdio>
using namespace std;
const int maxn = 50005;
int par[maxn];
int find_par(int x)
{
   return par[x]==x?x:par[x] = find_par(par[x]);
}

void Union(int x,int y)
{
    int fx = find_par(x);
    int fy = find_par(y);
    if(fx!=fy)
        par[fx]= fy;
}

int main()
{
    int m,n;
    int x,y;
    int t=0;
   while(scanf("%d%d",&n,&m)&&n)
    {
        for(int i=1;i<=n;i++)
            par[i] = i;
        for(int i=0;i<m;i++)
        {

            scanf("%d%d",&x,&y);
            Union(x,y);
        }
        int ans = 0;
        for(int i=1;i<=n;i++)
            if(find_par(i)==i)
                ans++;
        printf("Case %d: %d\n",++t,ans);

    }
    return 0;
}



FEATURED TAGS
数据结构
FRIENDS