并查集

发表于 | 分类于 |

前置知识:并查集的基本操作

基础并查集

并查集有两个基本操作，find与merge

通过路径压缩和按秩合并(启发式合并)来减小时间复杂度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void find(int x)
{
    return x==fa[x]?x:(fa[x]=find(fa[x]));
}//将查询链上的节点都直接指向根节点
void merge(int x,int y)
{
    x=find(x);
    y=find(y);
    if(rank[x]<rank[y])
    {
        swap(x,y);
    }
    fa[y]=x;
    if(x!=y)rank[x]=max(rank[y]+1,rank[x]);
}//rank可以理解为该集合的复杂度or最大可能深度，故总是将rank小的节点指向rank大的节点，rank也可采用集合的size

种类并查集

上述并查集可以维护集合之间的关系，如朋友的朋友是朋友，但如果我们引入敌人的关系，且敌人的敌人是朋友，无法用该并查集维护

类似于2-SAT，我们将第i个节点拆成i和i+n两个节点，x与y+n同属一个集合表示x与y是敌人

假设三个点，1和2是敌人，2和3是敌人

则1与3通过2+3相连，属于同一个集合，即朋友

带权并查集

并查集中的点、边带权值时，便使用带权并查集，通常使用val[i]来存储i到其父节点路径上的权值和,用size[i]维护i作父节点时，其集合节点总数

模板题:https://www.luogu.com.cn/problem/P1196

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
int init(int n)
{
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        size[i]=1;
        val[i]=0;
    }
}
int find(int x)
{
	if(x==fa[x]) return x;
    int A=find(fa[x]);
    val[x]+=val[fa[x]];
    return fa[x]=A;
}
int ask(int x,int y)
{
    int xx=find(x),yy=find(y);
    if(xx!=yy) return -1;//二者不在一个集合内
    return abs(val[x]-val[y])-1;//返回二者之间节点数
}
void merge(int x,int y)//x所在集合指向y所在集合
{
    int xx=find(x),yy=find(y);
    if(xx!=yy)
    {
        val[xx]=size[yy];
        size[yy]+=size[xx];
        fa[xx]=yy;
	}
}

find中，在路径压缩的同时，更新val[x]的值(新的val值为其旧父节点的新val值+其到旧父节点的val值)