Akira的OI(咸鱼)圈

并查集

算法
Word count: 279 / Reading time: 1 min
2018/09/02 Share

并查集的作用是快速的查询两个元素是否属于同一个集合。将除根节点外所有元素作为根节点的子节点(树的高度为2)即可得到O(1)的查询复杂度，这即是路径压缩。fa[i]即是i的父节点编号。如果两个节点有公共祖先，那么两节点在同一集合内。

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define ll long long
#define maxn 10001
using namespace std;
inline int read()
{
    int l=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        l=(l<<3)+(l<<1)+(ch^'0');
        ch=getchar();
    }
    return w*l;
}
int fa[maxn];
int find(int x)
{
    return x==fa[x]?x:fa[x]=find(fa[x]);
}
int main()
{
    int n,m,z,x,y;
    n=read(),m=read();
    for(int i=0;i<=n;i++)
        fa[i]=i;
    while(m--)
    {
        z=read(),x=read(),y=read();
        if(z==1)
            fa[find(x)]=find(y);
        else
            if(find(x)==find(y))
                printf("%c\n",'Y');
            else
                printf("%c\n",'N');
    }
    return 0;
}

原文作者: Akira

原文链接: https://akira-1231.github.io/2018/09/02/并查集/

发表日期: 九月 2日 2018, 1:43:23 下午

版权声明: 本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 11
2018
题解 算法 杂记