Criska

并查集

• 分类: 并查集 • 标签: 并查集

做了这么多套题，发现并查集的比例还是挺高的，但是我掌握的很不好orz，所以写一篇博客来熟悉一下并查集

1.并查集

并查集主要应用与判断两个元素是否处于同一个集合中，以及将新的元素加入集合中之类之类这样类似的问题。
那么从一开始，用father[x]记录x的父亲（意思即为x和它的父亲处于同一个集合中）。

1
2
3
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
	father[i]=i;

而且为了降低时间复杂度，我们要对元素进行路径压缩，就是让集合中的所有儿子指向同一个父亲。

2.判断元素是否处于同一个集合中

  • 简单来说我们只需要判断两个元素的父亲是不是一样的，就可以判断他们在不在同一个集合中。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    int find(x)//使用递归，并且进行路径压缩
    {
    	if(father[x]!=x)
    	father[x]=find(father[x]);
    	return father[x];
    }
    	for(int i=1;i<=m;++i)
    	{
    		scanf("%d%d",&x,&y);
    		int r1=find(x);
    		int r2=find(y);
    		if(r1!=r2) printf("NO/n");
    		else printf("YES/n");
    		
    	}

3.将新的元素加入集合中

首先进行判断，若x和y的父亲一样，那显然没必要进行更新。如果不一样，那么只需要将x的父亲指向y的父亲就可以了，意思就是x的父亲的父亲是y的父亲

1
2
3
4
5
6
7
8
9
10
11
12
int un(int r1,int r2)
{
	father[r2]=r1;
}
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&x,&y);
		int r1=find(x);
		int r2=find(y);
		if(r1!=r2) un(r1,r2);
	}

4.【模板】并查集

仍然是洛谷上一道并查集的裸题，附上代码

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<cstdio>
using namespace std;
int n,m,father[20000];
int un(int r1,int r2)
{
	father[r2]=r1;
}
int find(int x)
{
	if(father[x]!=x)
	father[x]=find(father[x]);
	return father[x];
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		father[i]=i;
	int k,x,y;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&k,&x,&y);
		int r1=find(x);
		int r2=find(y);			
		if(k==1)
		{
			if(r1!=r2) un(r1,r2);		
		}
		else
		{
			if(r1!=r2) printf("N\n");
			else printf("Y\n");			
		}
	}
	return 0;
}

5.【例题】旅行

【问题描述】
如果说旅行是令人愉悦的话，对于强迫症患者可不一定如此。
Alice 最近得到了一张旅行地图，其中详细标明了 A 市内的N个景点，共有M
条双向路连接着N个景点。由于 Alice的精力有限，她实在无法将N个景点全部游
遍，于是只好算了一个数字K，她只想详细游览前K个景点。受到强迫症的困扰，
Alice 特别害怕会在某个环上重复走来走去而导致可怕的事情发生，所以她希望
在地图上删去一些边，使得编号不大于K的所有景点都不在环上。

【输入格式】
从文件 tour .in 中读入数据。
输入的第一行是三个整数N,M, K。
接下来M行，每行有两个整数u, v描述一条无向边。

【输出格式】
输出到文件tour .out 中。
输出唯一一行，一个整数，表示最少删去的边数。

【样例输入】
11 13 5
1 2
1 3
1 5
3 5
2 8
4 11
7 11
6 10
6 9
2 3
8 9
5 9
9 10

【样例输出】
3
【评分标准】
对于每个测试点，你的输出必须和标准输出一致得到全部分数，否则不得分。

【数据规模及约定】
对于20%的数据,N ≤ 100,M ≤ 300.
对于40%的数据,N ≤ 1,000,M ≤ 5,000.
对于100%的数据,N≤ 1,000,000,M≤ 2,000,000, 1 ≤ K ≤ N.
数据保证不存在重边。

其实这道题的做法就是利用并查集

  • 对于小于k的点，如果两个点已经处于一个并查集中，那么显而易见，它们处于同一个环中，所以将ans++。如果并没有，那么将它们存入并查集
  • 对于大于k的点，直接存入并查集
  • 对于其他的点，先存下来，等到所有的点都判断完之后再考虑，如果不在环中就用并查集合并，否则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
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=2000000;
int n,m,k,a,b;
int xx[N],yy[N],father[N];
int find(int x)
{
	if(father[x]!=x) father[x]=find(father[x]);
	return father[x]; 
}
int un(int x,int y)
{
	father[find(x)]=find(y);
}
int main()
{
	freopen("tour.in","r",stdin);
	freopen("tour.out","w",stdout);
	scanf("%d%d%d",&n,&m,&k);
	int ans=0,cnt=0;
	for(int i=1;i<=n;++i) father[i]=i;
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		
		if(a>b)
		{
			int c=a;
			a=b;
			b=c;
		}
		if(b<=k)
		{
			if(find(a)==find(b)) ans++;
			else un(a,b);			
		}
		if(a>k)
		{
			un(a,b);			
		} 
		if(a<=k&&b>k)
		{
			xx[++cnt]=a;
			yy[cnt]=b;
		}
	}
	for(int i=1;i<=cnt;++i)
	{
		if(find(xx[i])==find(yy[i])) ans++;
		else un(xx[i],yy[i]);
	}
	printf("%d",ans);
	return 0;
}

【例题】银河英雄传说

  • 题意很好理解，显而易见我们要把M命令的x和y放入同一个并查集中，但是不好求的是对于C命令，x和y之间的战舰有多少。
  • r1/r2代表x/y的根节点，我们利用两个数组，va[x]记录的是x到根节点r1之间共有多少个战舰，而num[r1/r2]则记录每个并查集中共有多少个战舰，所以我们只需要在用路径压缩进行更新时将va[ ]数组和num[ ]进行更新就可以了。
  • 因此对于C命令，我们要求的就是va[x]和va[y]的差再减一就OK啦

附上代码

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
#include<iostream>
#include<cstdio>
using namespace std;
const int N=30001;
int t,fa[N],va[N],num[N],v;
int find(int x,int &pson)//由于return不能返回两个值，我们用&pson来更新fa[]，用return返回更新va[]
{
	if(fa[x]==x)
	{
		pson=x;
		return 0;
	}
	else
	{
		va[x]+=find(fa[x],fa[x]);
		pson=fa[x];
		return va[x];
	}
}
inline int un(int r1,int r2)
{
	fa[r1]=r2;
}
inline int qiu(int r1,int r2)
{
	va[r1]=num[r2];
	num[r2]+=num[r1];
	num[r1]=0;	//更新num[]和va[]值
}
int main()
{
	scanf("%d",&t);
	for(int i=1;i<=N;++i)
	{
		fa[i]=i;
		num[i]=1;
	}
	for(int i=1;i<=t;++i)
	{
		char h;
		int x,y;
		cin>>h;
		scanf("%d%d",&x,&y);
		int r1,r2;
		find(x,r1);
		find(y,r2);
		if(h=='M')
		{
			un(r1,r2);
			qiu(r1,r2);
		}
		else
		{
			if(r1==r2) 
			{
				if(va[x]>va[y])
				printf("%d\n",va[x]-va[y]-1);
				else printf("%d\n",va[y]-va[x]-1);
			}
			
			else printf("-1\n");
		}
	}
	return 0;
}

【例题】关押罪犯

  • 这是一个贪心+并查集的问题，刚开始想的太复杂了，考虑了所有的情况……其实并不用，我们只要将所有的犯罪组合按照冲突值从大到小进行排序，然后一个一个进行判断就可以了。
  • 那么，我们要尽可能让输出的值小，所以我们要尽可能地将较大的冲突值放入不同的子集中。秉承着“敌人的敌人就是朋友”，假设罪犯a和b需要放入两个不同的集合中，我们只需要将a放入b的敌人的集合中就可以了。
  • 具体实现见代码，是一种很神奇的并查集的方法： 将fa[n+i]设为fa[i]的敌人的集合，将a放入b的敌人的集合中，并在以后查询父亲的过程中（find）进行更新 。 
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
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=200000;
int n,m,fa[N],mark=0;
struct node{
	int a,b,c;
}e[N];
inline int find(int x)
{
	if(x!=fa[x]) fa[x]=find(fa[x]);
	return fa[x];
}
inline int cmp(const node & x,const node & y)
{
	return x.c>y.c;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=n*2;++i)//将fa[n+i]设为fa[i]的敌人的集合 
		fa[i]=i;
	for(int i=1;i<=m;++i)
	{
		int a,b,c,r1,r2;
		a=e[i].a;b=e[i].b;c=e[i].c;
		r1=find(a);
		r2=find(b);
		if(r1==r2)
		{
			printf("%d",c);
			mark=1;
			break;
		}
		fa[r1]=find(b+n);//将a放入b的敌人的集合中，并在以后进行更新 
		fa[r2]=find(a+n);
	}
	if(mark==0) printf("0");
	return 0;
}