种类并查集

Nannan Lv5
  2023-08-12 22:59 2023-08-12 22:59 Created   2024-09-30 19:52:52 2024-09-30 19:52:52 Updated      

种类并查集

一、种类并查集定义

定义：把一个集合中的元素根据他们的不同关系进行分类与合并。朋友的朋友是朋友。敌人的敌人也是朋友。种类并查集做的事情就是：不让两个有敌对关系的人在同一个队伍里面。

二、几个比较板的题目

例题1： [P2024 NOI2001] 食物链

思路：中动物构成吃与被吃的关系。题目里面说了，总共就三类动物，构成的关系是

那么我们的做法是，将到个元素扩大到三倍。以下是含义的解释：

元素，元素,元素三者的关系被定义为：

  1. 所在集合中所有的元素都是的同类
  2. 所在集合中所有的元素都是的天敌
  3. 所在集合中所有的元素都是的猎物
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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010,M = 2e6+10;

struct DSU
{
	vector<int>fa,s;
	int cnt;//连通块数量.
	DSU(int n=1):fa(n+1,-1),s(n+1,1),cnt(n){}
	int size(int x){return s[find(x)];}
	int find(int x){return fa[x]==-1?x:fa[x]=find(fa[x]);}
	
	bool connect(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return true;
		else return false;
	}
	
	void merge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return ;
		s[x]+=s[y];
		fa[y]=x;
	}
};
int n,m;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	DSU dsu(n*3);
	int cnt = 0;
	for(int i = 1;i<=m;i++)
	{
		int ty,x,y;
		cin>>ty>>x>>y;
		if(x>n||y>n){cnt++;continue;}
		if(ty==1)
		{
			if(dsu.connect(x,y+n)||dsu.connect(x,y+n*2))
				cnt++;
			else
				dsu.merge(x,y),dsu.merge(x+n,y+n),dsu.merge(x+n*2,y+n*2);
		}
		else{
			if(dsu.connect(x,y)||dsu.connect(x,y+n*2))
				cnt++;
			else
				dsu.merge(x,y+n),dsu.merge(x+n,y+n+n),dsu.merge(x+n+n,y);
		}
	}
	cout<<cnt<<"\n";
	return 0;
}

例题2：P1525关押罪犯

思路：思路和上一题一样，我们开2倍数组。表示朋友，表示敌人。为了得到最大怨气值最小，我们先按照怨气值从大到小排序，先解决怨气大的，第一个不能解决的就是答案。注意如果全都解决了，答案是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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+10;

struct ty
{
	int u,v,w;
}a[N];

bool cmp(ty a,ty b)
{
	return a.w>b.w;
}

struct DSU
{
	vector<int>fa,s;
	int cnt;//连通块数量.
	DSU(int n=1):fa(n+1,-1),s(n+1,1),cnt(n){}
	int size(int x){return s[find(x)];}
	int find(int x){return fa[x]==-1?x:fa[x]=find(fa[x]);}
	
	bool connect(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return true;
		else return false;
	}
	
	void merge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return ;
		s[x]+=s[y];
		fa[y]=x;
	}
};

int n,m;

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=m;i++)
		cin>>a[i].u>>a[i].v>>a[i].w;
	sort(a+1,a+1+m,cmp);
	DSU dsu(n*2+1);
	for(int i = 1;i<=m;i++)
	{
		int u = a[i].u,v = a[i].v,w = a[i].w;
		if(dsu.connect(u,v)||dsu.connect(u+n,v+n))
		{
			cout<<w<<"\n";
			return 0;
		}
		dsu.merge(u,v+n);
		dsu.merge(u+n,v);
	}
	cout<<0<<"\n";
	return 0;
}

例题3：P1892 团伙

思路：同样是开2倍数组，因为朋友的朋友是朋友，敌人的敌人也是朋友。那么如果是朋友，我们直接合并。如果是敌人，我们把敌人的敌人合并起来。比如和是敌人，那么我们就把和合并起来。最后统计有几个集合就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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int n,m,fa[N];
int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i = 1;i<=n*2;i++)
		fa[i] = i;
	for(int i = 1;i<=m;i++)
	{
		char ty;
		int u,v;
		cin>>ty>>u>>v;
		if(ty=='F')
		{
			fa[find(u)] = find(v);
		}
		else
		{
			fa[find(u+n)] = find(v);
			fa[find(v+n)] = find(u);
		}
			
	}
	int cnt = 0;
	for(int i = 1;i<=n;i++)
		if(fa[i]==i)
			cnt++;
	cout<<cnt<<"\n";
	return 0;
}

例题4：P1955 程序自动分析

思路：首先我们要明确的是：相等关系可以传递，不等关系是不能传递的！所以不能和之前那样单纯的分两种。那该怎么办呢？我们考虑变更维护顺序。如果是相等关系，我们直接合并。如果是不等关系，我们先离线存起来，相等关系处理完了，我们统一处理不等关系。如果两个不等的在同一个集合里面说明不满足。

注意：数组开$2n因为n是总关系数，所以至多出现2n个x$。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6+10;
int n,m,fa[N];
int find(int x)
{
	if(x==fa[x])return x;
	return fa[x] = find(fa[x]);
}
void merge(int x,int y)
{
	x=find(x),y=find(y);
	if(x==y)return ;
	fa[y]=x;
}
map<int,int>mp;
vector<pair<int,int>>event;
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		mp.clear();
		event.clear();
		cin>>n;
		int cnt = 0;
		for(int i = 1;i<=2*n;i++)
			fa[i] = i;
		bool ok = true;
		for(int i = 1;i<=n;i++)
		{
			int u,v,ty;
			cin>>u>>v>>ty;
			if(!mp[u])mp[u] = ++cnt;
			if(!mp[v])mp[v] = ++cnt;
			if(ty==1)
			{
				merge(mp[u],mp[v]);
			}
			else
			{
				event.push_back({mp[u],mp[v]});
			}
		}
		for(auto [u,v]:event)
		{
			if(find(u)==find(v)){

				ok = false;
				break;
			}
		}
		if(ok)cout<<"YES\n";
		else cout<<"NO\n";

	}
	return 0;
}

三、有一点小trick的题

例题5：P1196 银河英雄传说

思路：有两种操作，一种是讯问，一种是把一个集合和另一个集合拼接。需要注意的是find和merge函数的写法。因为我们还需要维护每个点到头节点的距离，以及每个集合的大小。具体代码里面有写。

每个元素到头节点的距离

每个集合的大小

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+10;
int fa[N],s[N],toh[N];

int find(int x){
	if(fa[x]==x)
		return x;
	int f1 = fa[x],f2 = find(fa[x]);
	fa[x] = f2;
	toh[x] += toh[f1];
	/*
	  因为我们进行了路径压缩，所以这个点到父亲的距离
	  要加上新压缩的路径中未被计算的点
	 */
	return f2;
}

bool connect(int x,int y)
{
	x =find(x),y=find(y);
	if(x==y)return true;
	else return false;
}

void merge(int x,int y)
{
	int f1 = find(x),f2 = find(y);
	if(f1==f2)return;
	fa[f2] = f1;
	toh[f2] = s[f1];//父亲到新头节点距离就是,原列长度。
	s[f1]+=s[f2];//f1后面放了s[f2]个
	s[f2] = 0;
}


int n,m;

int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i = 1;i<=30000;i++)
		fa[i] = i,s[i] = 1;
	int t;
	cin>>t;
	while(t--)
	{
		char ty;
		int u,v;
		cin>>ty>>u>>v;
		if(ty=='M')
		{
			merge(v,u);
		}
		else{
			if(!connect(u,v))
				cout<<-1<<"\n";
			else cout<<abs(toh[u]-toh[v])-1<<"\n";
		}
	}
	return 0;
}
  • Title: 种类并查集
  • Author: Nannan
  • Created at : 2023-08-12 22:59:00
  • Updated at : 2024-09-30 19:52:52
  • Link: https://redefine.ohevan.com/2023/08/12/四(4)、种类并查集/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
种类并查集
  1. 种类并查集
    1. 一、种类并查集定义
    2. 二、几个比较板的题目
      1. 例题1： [P2024 NOI2001] 食物链
      2. 例题2：P1525关押罪犯
      3. 例题3：P1892 团伙
      4. 例题4：P1955 程序自动分析
    3. 三、有一点小trick的题
      1. 例题5：P1196 银河英雄传说