zcmu--1435--1930（并查集）

目录

zcmu-1435: 盟国（带删除的并查集）

zcmu-1930: 帽子戏法

1435: 盟国

Time Limit: 3 Sec  Memory Limit: 128 MB
Submit: 457  Solved: 105
[Submit][Status][Web Board]

Description

世界上存在着N个国家，简单起见，编号从0~N-1，假如a国和b国是盟国，b国和c国是盟国，那么a国和c国也是盟国。另外每个国家都有权宣布退盟（注意，退盟后还可以再结盟）。

定义下面两个操作：

“M X Y” ：X国和Y国结盟  (如果X与Z结盟,Y与Z结盟,那么X与Y也自动结盟).

“S X” ：X国宣布退盟 (如果X与Z结盟,Y与Z结盟,Z退盟,那么X与Y还是联盟).

Input

多组case。

每组case输入一个N和M (1 ≤ N ≤ 100000 , 1 ≤ M ≤ 1000000),N是国家数，M是操作数。

接下来输入M行操作

当N=0，M=0时，结束输入

Output

对每组case输出最终有多少个联盟(如果一个国家不与任何国家联盟,它也算一个独立的联盟)，格式见样例。

Sample Input

5 6

M 0 1

M 1 2

M 1 3

S 1

M 1 2

S 3

3 1

M 1 2

0 0

Sample Output

Case #1: 3

Case #2: 2

HINT

 带删除并查集

Source

FZU

【分析】带删除的并查集。主要理解的就是，删除的时候，使它指向n++。（详解戳这）

   然后，，这里是一行代码的并查集........

int find(int x){ return fa[x]==-1?x:fa[x]=find(fa[x]); }

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=1000005;
int fa[maxn],id[maxn],vis[maxn];
int find(int x)
{ 
	return fa[x]==-1?x:fa[x]=find(fa[x]); 
}
int main()
{
	int n,m,ca=0;
	while(~scanf("%d%d",&n,&m)&&n&&m)
	{
		for(int i=0;i<n;i++)id[i]=i;
		memset(fa,-1,sizeof(fa));
		int t=n;
		while(m--)
		{
			char ch;
			ch=getchar();
			while(ch!='M'&&ch!='S')ch=getchar();
			int x,y,z;
			if(ch=='M')
			{
				scanf("%d%d",&x,&y);
				x=id[x],y=id[y];
				int xx=find(x);
				int yy=find(y);
			//	cout<<xx<<","<<yy<<endl;
				if(xx!=yy)fa[xx]=yy;
			}
			else
			{
				scanf("%d",&z);
				id[z]=t++;
			}
		}
		int ans=0;
		memset(vis,-1,sizeof(vis));
		for(int i=0;i<n;i++)
		{
			int x=find(id[i]);
		//	cout<<"x="<<x<<",id[i]="<<id[i]<<",vis[x]="<<vis[x]<<endl;
			if(vis[x]==-1)
			{
				vis[x]=1;ans++;
			}
		}
		printf("Case #%d: %dn",++ca,ans);
	}
	return 0;
}

1930: 帽子戏法（并查集）

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 82  Solved: 22
[Submit][Status][Web Board]

Description

小A家有很多很多顶帽子初始时帽子都是独立分开的,每顶帽子都有一个编号用于区分.小A会有以下操作之一:
1.将编号为y的帽子所在的帽子堆放在编号为x的帽子所在的帽子堆顶上,如果x,y在同一堆则不做任何动作.
2.小A会向你询问编号为x的帽子上方有多少只帽子.

Input

输入有多组数据:
第一行输入N,M分别为帽子数和操作数(1<=N<=40000,1<=M<=400000)
帽子的编号对应1,2,3...,N.
接下来有M行输入为 T x y 对应操作1. Q x 对应操作2.

Output

对于小A的询问输出位于编号为x的帽子上方的帽子数.

Sample Input

2 2

T 1 2

Q 1

Sample Output

1

HINT

Source

lcf

【分析】

定义3个数组，fa[i] 记录每个点的前驱节点，num[i] 记录每个帽子上面有多少帽子，pos[i]记录每个帽子堆有多少帽子，i表示这堆帽子最上面的那个帽子（选择最上面的那个帽子，在更新的时候，直接将堆顶即两个帽子更新即可）。在进行移动操作时，如果帽子在同一堆的话，就不再操作。

帽子应该的结构是这样的：

在合并操作的同时，记录了每个点的num[i]，所以，在右边的结构中，相对顺序是无所谓的，已经知道了某点的num[i]，比如2，已经知道了2上面有多少个点。

int find(int x)
{
	if(x!=fa[x])
	{
		int xx=fa[x];
		fa[x]=find(fa[x]);
		num[x]+=num[xx];//在这里记录x上面有多少顶帽子 
	}
	return fa[x];
}

数组pos[i]，

【代码】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=4e5+5;
int fa[maxn],num[maxn],pos[maxn];
int find(int x)
{
	if(x!=fa[x])
	{
		int xx=fa[x];
		fa[x]=find(fa[x]);
		num[x]+=num[xx];
	}
	return fa[x];
}
int main()
{
	int n,m;
	while(~scanf("%d%d",&n,&m))
	{
		for(int i=0;i<n;i++)fa[i]=i,num[i]=0,pos[i]=1;
		while(m--)
		{
			char ch=getchar();
			while(ch!='T'&&ch!='Q')ch=getchar();
			if(ch=='T')
			{
				int x,y;
				scanf("%d%d",&x,&y);
				int xx=find(x),yy=find(y);
				if(xx!=yy)
				{
					fa[xx]=yy;//将y移动到x，即x指向y
					num[xx]+=pos[yy];
					pos[yy]+=pos[xx]; 
				}
			}
			else
			{
				int x;
				scanf("%d",&x);
				find(x);
				printf("%dn",num[x]);
			}
		}
	}
	return 0;
}

最后

以上就是粗犷樱桃最近收集整理的关于zcmu--1435--1930（并查集）的全部内容，更多相关zcmu--1435--1930（并查集）内容请搜索靠谱客的其他文章。