并查集 Suspects Cube stacking

POJ1611 The Suspects
n个学生分属m个团体，(0 < n <= 30000 , 0
<= m <= 500) 一个学生可以属于多个团体。
一个学生疑似患病，则它所属的整个团体都
疑似患病。已知0号学生疑似患病，以及每个
团体都由哪些学生构成，求一共多少个学生
疑似患病。
解法：最基础的并查集,把所有可疑的都并一
块。
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 30000;
int n,m,k;
int parent[MAX+10];
int total[MAX+10];
//total[GetRoot(a)]是a所在的group的人数
int GetRoot(int a)
{ //获取a的根,并把a的父节点改为根
if( parent[a]!= a)//不是根节点
parent[a] =
GetRoot(parent[a]);//a的父亲等于父亲的父亲
return parent[a];
}
void Merge(int a,int b)
{
int p1 = GetRoot(a);
int p2 = GetRoot(b);
if( p1 == p2 )
return;
total[p1] += total[p2];//总长度
parent[p2] = p1;//改变父节点
}
int main() 
{
  while(true) 
  {
scanf("%d%d",&n,&m);
if( n == 0 && m == 0)  break;
for(int i = 0;i < n; ++i) {
parent[i] = i;  total[i] = 1;
}
for(int i = 0;i < m; ++i) 
{ int h,s;
scanf("%d",&k); scanf("%d",&h);
for( int j = 1; j < k; ++j) 
 {
scanf("%d",&s);//与刚刚输入的第一个
Merge(h,s);//合并
 }
}
printf("%d\n",total[GetRoot(0)]); 
}
return 0;
}

POJ 1988 Cube stacking
有N(N<=30,000)堆方块，开始每堆都是一个
方块。方块编号1 – N. 有两种操作：
M x y ： 表示把方块x所在的堆，拿起来叠放
到y所在的堆上。
C x : 问方块x下面有多少个方块。
操作最多有 P (P<=100,000)次。对每次C操
作，输出结果。
解法：
除了parent数组，还要开设
sum数组：记录每堆一共有多少方块。
若parent[a] = a, 则sum[a]表示a所在的堆的
方块数目。
under数组，under[i]表示第i个方块下面有多少
个方块。
under数组在 堆合并和 路径压缩的时候都要更
新。

#include <iostream>
#include <cstdio>
using namespace std;
const int MAX = 31000;
int parent[MAX];
int sum[MAX]; // 若parent[i]=i,sum[i]表示砖块i所在堆的砖块数目
int under[MAX]; // under[i]表示砖块i下面有多少砖块
int GetRoot(int a)
{//获取a的根,并把a的父节点改为根
if( parent[a] == a)
return a;
int t = GetRoot(parent[a]);
under[a] += under[parent[a]];
parent[a] = t;
return parent[a];
}
void Merge(int a,int b)
//把b所在的堆，叠放到a所在的堆。
{  int n;
int pa = GetRoot(a);
int pb = GetRoot(b);
if( pa == pb )
return ;
parent[pb] = pa;//根为pa
under[pb] = sum[pa]; //under[pb] 赋值前一定是0，因为
//parent[pb] = pb,pb一定是原b所在堆最底下的
//under等于父节点的sum
sum[pa] += sum[pb];
}
int main()
{
int p;
for(int i = 0; i < MAX; ++ i) {//初始化
sum[i] = 1;
under[i] = 0;
parent[i] = i;
}
scanf("%d",&p);
for( int i = 0;i < p; ++ i) {
char s[20];  int a,b;
scanf("%s",s);
if( s[0] == 'M') {
scanf("%d%d",&a,&b);
Merge(b,a);
}
else {
scanf("%d",&a);
GetRoot(a);
printf("%d\n",under[a]);
}
}
return 0;
}

来自于北京大学暑期课《ACM/ICPC竞赛训练》
北京大学信息学院 郭炜老师