mydcwfy's Blog

并查集

Posted on
Symbols count in article: 5.3k Reading time ≈ 12 mins.

简单的前置知识。

并查集

1.基本操作

并查集维护的是一种关系，这种关系具有传递性，并且一般具有对称性。

1）merge: 将两个集合合并

2）find: 查询代表元素

1
2
3
4
5
6
7
8
9
10
11
int find(int x)
{
    if (p[x]==x) return p[x];
    return p[x]=find(p[x]);
}

void merge(int a,int b)
{
    int root_a=find(a),root_b=find(b);
    p[root_b]=root_a;
}

易得，并查集是树形结构。

2.优化

1）路径压缩：$O(\log(n))$

2）按秩合并：$O(\log(n))$

一般来说，只需要用第一个即可。

由于常数很小，实际用时，可以看做 $O(1)$

3.扩展

1）记录集合大小：一般保存到代表元素。

2）每个点到根节点的距离：绑定到每一个元素。

比如说 [NOI2001] 食物链

题目传送门 Luogu

题目传送门 AcWing

有两种处理方式：边带权和扩展域。

我们后面再讲。

4.例题

T1：格子游戏

来自 《信息学奥赛一本通》（但多方都没有找到）

将连边的两个点合并到一个并查集即可。

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define get(i,j) (i-1)*n+j
using namespace std;

const int N=205*205;
int n,m,p[N];

int find(int x)
{
    if (p[x]==x) return p[x];
    return p[x]=find(p[x]);
}

void merge(int a,int b)
{
    int root_a=find(a),root_b=find(b);
    p[root_b]=root_a;
}

int main()
{
    cin>>n>>m;
    char op[5];
    int a,b;
    for (int i=1;i<=n*n;++i) p[i]=i;
    for (int i=1;i<=m;++i)
    {
        scanf("%d%d%s",&a,&b,op);
        int x=get(a,b);
        int y;
        if (op[0]=='D') y=get(a+1,b);
        else y=get(a,b+1);
        x=find(x);y=find(y);
        if (x==y)
        {
            printf("%d",i);
            return 0;
        }
        merge(x,y);
    }
    puts("draw");
    return 0;
}

T2：搭配购买

题目传送门 Luogu

注意维护根节点的价钱和价值。

最后是一个 01 背包。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;

const int N=1e4+10;

int p[N],v[N],w[N],n,m,f[int(1e7)],tot;

int find(int x)
{
    if (p[x]==x) return p[x];
    return p[x]=find(p[x]);
}

int main()
{
    cin>>n>>m>>tot;
    for (int i=1;i<=n;++i) p[i]=i;
    for (int i=1;i<=n;++i) scanf("%d %d",v+i,w+i);
    int a,b,x,y;
    while (m--)
    {
        scanf("%d %d",&a,&b);
        x=find(a);y=find(b);
        if (x!=y)
        {
            w[x]+=w[y];
            v[x]+=v[y];
            p[y]=x;
        }
    }
    for (int i=1;i<=n;++i)
    {
        if (p[i]!=i) continue;
        for (int j=tot;j>=v[i];--j)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    }
    cout<<f[tot]<<endl;
    return 0;
}

T3：[NOI2015] 程序自动分析

题目传送门 Luogu

题目传送门 AcWing

考虑由于等于具有传递性，而不等于不具有传递性，所以将相互等于的数维护一个并查集即可。

数据范围较大，需要离散化。

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
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<unordered_map>
using namespace std;

const int N=1e5+10;
unordered_map <int,int> S;
int n,m,p[N*2];

struct Q{
    int a,b,e;
}q[N];

int get(int x)
{
    if (S.count(x)==0) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if (x==p[x]) return x;
    return p[x]=find(p[x]);
}

int main()
{
    int t,x,y,e;cin>>t;
    while (t--)
    {
        n=0;
        S.clear();
        cin>>m;
        for (int i=1;i<=m;++i)
        {
            scanf("%d %d %d",&x,&y,&q[i].e);
            q[i].a=get(x),q[i].b=get(y);
        }
        for (int i=1;i<=n;++i) p[i]=i;
        for (int i=1;i<=m;++i)
            if (q[i].e) p[find(q[i].a)]=find(q[i].b);
        bool flag=1;
        for (int i=1;i<=m;++i)
            if (!q[i].e)
                if (find(q[i].a)==find(q[i].b))
                {
                    flag=0;
                    break;
                }
        puts(flag?"YES":"NO");
    }
    return 0;
}

T4：[NOI2002] 银河英雄传说

题目传送门 Luogu

题目传送门 AcWing

如果没有询问距离，怎么办？

很简单，直接并查集即可。

可以发现，从 $x$ 到 $y$ 的距离，可以与 $x$,$y$ 到根节点的距离有关。

每当合并时，将被合并的点加一个前面的 $size[x]$。

前面讲到，因为是一个树形结构，所以它的子节点要路径压缩时，必定会经过被合并的点，并加上该点的 $d[x]$。

同时可以得到：

注意特判 $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
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;

const int N=3e5+10;
int p[N],n,d[N],s[N];

int find(int x)
{
    if (p[x]==x) return x;
    int rt=find(p[x]);
    d[x]+=d[p[x]];
    return p[x]=rt;
}

int main()
{
    for (int i=0;i<N;++i) p[i]=i,s[i]=1;
    cin>>n;
    char op[2];
    int a,b;
    while (n--)
    {
        scanf("%s%d%d",op,&a,&b);
        int x=find(a),y=find(b);
        if (op[0]=='M')
        {
            if (x==y) continue;
            d[x]=s[y];
            s[y]+=s[x];
            p[x]=y;
        }
        else
        {
            if (x!=y) puts("-1");
            else printf("%d\n",max(abs(d[a]-d[b])-1,0));
        }
    }
    return 0;
}

T5：奇偶游戏

题目传送门 AcWing

观察到 $N$ 很大，而 $M$ 相对小得多。

考虑离散化。

记录前缀和 $s[i]=\sum_{j=1}^{i}a[j]$

如果 $l-r$ 中有奇数个，等价于 $s(r)$ 与 $s(l-1)$ 奇偶性不同。

每次将其奇偶性得到，如果出现矛盾，则不行。

但是，如果没有矛盾，一定可以吗？( 雾 )

答案是肯定的。

直接使 $a[i]=|s[i]-s[i-1]|$ ，就一定满足条件。

现在，我们要维护有关联的点，作为一个并查集。

我们先用边带权做一次。

$d[x]$ 表示 $x$ 到根节点的奇偶性，则 $dis(x,y)=d[x]+d[y]$。

每当插入一个关系时，我们应该先判断是否合法。

如果不在一个集合，那么我们连接 $px$ 与 $py$，边权为 $d[px]=d[x]$ ^ $d[y]$ ^ $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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<unordered_map>
using namespace std;

const int N=2e5+10;
unordered_map <int,int> S;
int n,m,tot,p[N],d[N];

int get(int x)
{
    if (S.count(x)==0) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if (p[x]==x) return p[x];
    int rt=find(p[x]);
    d[x]^=d[p[x]];
    return p[x]=rt;
}

int main()
{
    char op[10];
    int a,b;
    cin>>tot>>m;
    for (int i=0;i<N;++i) p[i]=i;
    for (int i=1;i<=m;++i)
    {
        scanf("%d %d %s",&a,&b,op);
        a=get(a-1);b=get(b);
        int x=find(a),y=find(b);
        if (op[0]=='e')
        {

            if (x!=y) p[x]=y,d[x]=d[a]^d[b];
            else
            {
                if (d[a]^d[b])
                {
                    cout<<i-1<<endl;
                    return 0;
                }
            }
        }
        else if (op[0]=='o')
        {
            if (x!=y) p[x]=y,d[x]=d[a]^d[b]^1;
            else
            {
                if (d[a]^d[b]==0)
                {
                    cout<<i-1<<endl;
                    return 0;
                }
            }
        }
        else while (1);
    }
    cout<<m<<endl;
    return 0;
}

扩展域先鸽着。