并查集

 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
68
69

(1)朴素并查集：

    int p[N]; //存储每个点的祖宗节点

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);


(2)维护size的并查集：

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);


(3)维护到祖宗节点距离的并查集：

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

 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

#include<iostream>
using namespace std;

const int N = 100010;

int n,m;
int p[N];

int find(int x) //返回x的祖宗结点 + 路径压缩
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        p[i] = i;
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if (op[0] == 'M')
            p[find(a)] = find(b);
        else
        {
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    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

//本次思路即为合并集合的稍微变形
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 100010;
int n, m;
int p[N];
int siz[N];
int find(int x)//合并集合并且压缩路径
{
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		p[i] = i;
		siz[i] = 1;
	}
	while (m--)
	{
		char op[2];
		int a, b;
		scanf("%s", op);
		if (op[0] == 'C')
		{
			scanf("%d%d", &a, &b);
			if (find(a) == find(b)) continue;//当ab已经为同一根节点是，跳出本次循环继续下次循环
			siz[find(b)] += siz[find(a)];//尺度合并
			p[find(a)] = find(b);//合并两个集合
		}
		else if (op[1] == '1')
		{
			scanf("%d%d", &a, &b);
			if (find(a) == find(b)) printf("Yes\n");
			else printf("No\n");
		}
		else
		{
			scanf("%d", &a);
			printf("%d", siz[find(a)]);
		}
	}
	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

#include<bits/stdc++.h>
using namespace std;
int sz[30010],d[30010],fa[30010];
int find(int x)
{
    if(fa[x]!=x)
    {
        int root=find(fa[x]);
        d[x]+=d[fa[x]];
        fa[x]=root;
    }
    return fa[x];
}
int main()
{
    int t;
    for(int i=0;i<30010;i++) d[i]=0,sz[i]=1,fa[i]=i;

    cin>>t;
    while(t--){
        char op;
        int a,b;
        cin>>op>>a>>b;
        //scanf("%s%d%d",op,&a,&b);
        int pa=find(a),pb=find(b);
        if(op=='M'){
            if(pa!=pb)
            {
                fa[pa]=pb;
                d[pa]=sz[pb];
                sz[pb]+=sz[pa];
            }
        }
        else{
            if(pa!=pb) cout<<-1<<endl;
            else printf("%d\n",max(0,abs(d[a]-d[b])-1));
        }
    }
    return 0;
}