病毒
Time Limit: 1000 MS Memory Limit: 65536 K
Total Submit: 719(185 users) Total Accepted: 247(163 users) Rating: Special Judge: No
Description
某种病毒袭击了某地区，该地区有N(1≤N≤50000)人，分别编号为0,1,...,N-1，现在0号已被确诊，所有0的直接朋友和间接朋友都要被隔离。例如：0与1是直接朋友，1与2是直接朋友，则0、2就是间接朋友，那么0、1、2都须被隔离。现在，已查明有M(1≤M≤10000)个直接朋友关系。如：0,2就表示0,2是直接朋友关系。
请你编程计算，有多少人要被隔离。
Input
第一行包含两个正整数N(1≤N≤50000),M(1≤M≤100000)，分别表示人数和接触关系数量；
在接下来的M行中，每行表示一次接触，；
每行包括两个整数U, V(0 <= U, V < N)表示一个直接朋友关系。
Output
输出数据仅包含一个整数，为共需隔离的人数（包含0号在内）。
Sample Input
100 4
0 1
1 2
3 4
4 5
Sample Output
3
并查集，入门题。
思路是先根据关系建立关系树，然后记录0号小朋友的根节点，依次与剩下所有的小朋友的根节点比较，相等则计数+1，表示这是和0号小朋友有关系的，即被感染的人。最后输出总计数（即被0号小朋友感染的人数）。
套模板很容易过。
代码：
#include <stdio.h> /* 并查集模板
*/
int UFS_NUM; //并查集中元素总数
typedef struct node{
int data; //节点对应的编号
int rank; //节点对应秩
int parent; //节点对应的双亲下标
}UFSTree; //并查集树的节点类型
void MAKE_SET(UFSTree t[]) //初始化并查集树
{
int i;
for(i=;i<UFS_NUM;i++){
t[i].data = i; //数据为该点编号
t[i].rank = ; //秩初始化为0
t[i].parent = i; //双亲初始化为指向自己
}
}
int FIND_SET(UFSTree t[],int x) //在x所在的子树中查找集合编号
{
if(t[x].parent == x) //双亲是自己
return x; //双亲是自己，返回 x
else //双亲不是自己
return FIND_SET(t,t[x].parent); //递归在双亲中查找x
}
void UNION(UFSTree t[],int x,int y) //将x和y所在的子树合并
{
x = FIND_SET(t,x); //查找 x 所在分离集合树的编号
y = FIND_SET(t,y); //查找 y 所在分离集合树的编号
if(t[x].rank > t[y].rank) //y 节点的秩小于 x节点的秩
t[y].parent = x; //将 y 连接到 x 节点上，x 作为 y 的双亲节点
else{ //y 节点的秩大于等于 x 节点的秩
t[x].parent = y; //将 x 连接到 y 节点上，y 作为 x 的双亲节点
if(t[x].rank==t[y].rank) //x 和 y的双亲节点秩相同
t[y].rank++; //y 节点的秩增 1
}
}
int main()
{
int i,n,m,x,y;
while(scanf("%d%d",&n,&m)!=EOF){
UFSTree t[];
UFS_NUM = n;
MAKE_SET(t);
for(i=;i<=m;i++){
scanf("%d%d",&x,&y);
UNION(t,x,y);
}
int f0 = FIND_SET(t,);
int sum=;
for(i=;i<n;i++)
if(FIND_SET(t,i)==f0)
sum++;
printf("%d\n",sum);
}
return ;
}
Freecode : www.cnblogs.com/yym2013