FJUT—2144 并查集

FJUT—2144 并查集"/>

FJUT—2144 并查集

并查集

TimeLimit:3000MS  MemoryLimit:128MB

64-bit integer IO format:%lld

已解决 | 点击收藏

Problem Description

并查集详解：

这里注意一下，用递归压缩路径的同学，可能会爆栈，从而导致Runtime Error 建议用循环压缩路径

Input

输入多组数据

每组数据第一行是两个整数n（1<=n<=10^6），m(1<=m<=10^6)。分别表示元素数、操作数（初始时每个元素以自己为一个集合,元素编号是1-n）

接下来m行，每行有如下几种输入：

union x y ——表示将x所在的集合和y所在的集合合并为一个集合。

same x y ——询问x和y是否为同一个集合、为同一个集合输出1，不同集合输出0

num x ——询问x所在的集合共有多少个元素

max x ——询问x所在的集合中元素编号最大是多少

setnum ——询问现在总共有多少个集合

Output

对于每个same、num、max、setnum操作输出一行，用一个整数表示答案。

Sample Input

5 10
setnum
same 1 2
union 1 2
same 1 2
union 2 3
same 1 3
union 4 5
setnum
max 1
num 4

Sample Output

5
0
1
1
2
3
2

AC Code(注意：此题只能用循环压缩路径，不能用递归压缩路径)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int nmax=1e6+10;
int father[nmax];
int maxx[nmax];//最大元素编号
int num[nmax];//集合中的元素数//递归压缩路径会爆栈 
int findFather(int x)//循环压缩路径 
{int p,tmp;p = x;while(x != father[x])//找到x的根节点 x =  father[x];while(p!= x){tmp= father[p];father[p] = x;p = tmp;}return x;
}
void init(int n){for(int i=1;i<=n;i++){father[i]=i;num[i]=1;//每个集合只有1个元素maxx[i]=i;//最大元素初始化为自己 } 
}
void Union(int u,int v){int fu=findFather(u);int fv=findFather(v);if(fu!=fv){father[fu]=fv;//fv是根maxx[fv]=max(maxx[fu],maxx[fv]) ;//根的最大元素=max(fu、fv最大元素);num[fv]=num[fu]+num[fv]; }
}int main(int argc, char** argv) {int n,m;//元素数、操作数char s[10];while(scanf("%d %d",&n,&m)!=EOF){int Set=n;memset(father,0,sizeof(father));memset(num,0,sizeof(num));memset(maxx,0,sizeof(maxx));init(n);for(int i=0;i<m;i++){scanf("%s",s);int x,y;if(s[0]=='u'){//unionscanf("%d %d",&x,&y);if(findFather(x)!=findFather(y)){Union(x,y);Set--;} }if(s[0]=='s' && s[1]=='a'){//same，判断x和y是否为同一个集合 scanf("%d %d",&x,&y);if(findFather(x)==findFather(y)) puts("1");else puts("0"); }if(s[0]=='n'){//num,查询集合共有多少个元素scanf("%d",&x);printf("%d\n",num[findFather(x)]); } if(s[0]=='m'){//max，询问x所在的集合中元素编号最大是多少 scanf("%d",&x);printf("%d\n",maxx[findFather(x)]); }if(s[0]=='s' && s[1]=='e'){//setnum，询问现在总共有多少个集合 printf("%d\n",Set);}}} return 0;
}