关于SARS病毒传染的问题。在同一个组的学生是接触很近的，后面也会有新的同学的加入。其中有一位同学感染SARS，那么该组的所有同学得了SARS。要计算出有多少位学生感染SARS了。编号为0的同学是得了SARS的。
直接用并查集解决水掉
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<string>
#include<algorithm>
#include<iomanip>
using namespace std;
#define MAX 100 struct node
{
int no;//编号
int rank;
int parent;
int total;
}; class DisJoinSet
{
protected:
int n;
node * tree;
public:
DisJoinSet(int n );
~DisJoinSet();
void Init();
void Union(int x,int y);
int Find(int x);
int GetAswer(int x);
}; DisJoinSet ::DisJoinSet(int n)//初始化操作
{
this->n = n;
tree = new node[n];
for(int i = ; i < n; i++)
{
tree[i].no = i;
tree[i].parent = i;
tree[i].total = ;
tree[i].rank = ;
}
}
DisJoinSet::~DisJoinSet()
{
delete[] tree;
} void DisJoinSet :: Init()
{
}
int DisJoinSet::Find(int x)
{
int temp = tree[x].parent;//temp 为x的父亲结点
if( x != tree[x].parent)
{
tree[x].parent = Find(tree[x].parent);//路径压缩
return tree[x].parent;
}
else
{
return x;
}
} void DisJoinSet ::Union(int x,int y)
{
int rootx = Find(x);
int rooty = Find(y);
if(rootx == rooty)
{
return ;
}
else//并查集基本操作
{
if(tree[rootx].rank < tree[rooty].rank)
{
tree[rootx].parent = rooty;
tree[rooty].total += tree[rootx].total;
}
else
{
tree[rooty].parent = rootx;
tree[rootx].total += tree[rooty].total;
if(tree[rootx].rank == tree[rooty].rank)
{
tree[rootx].rank++;
}
}
}
} int DisJoinSet::GetAswer(int x)//返回xtotal
{
int t = Find(x);
return tree[t].total;
} int main()
{
int n;
int m;
while(cin>>n>>m && n!= && m>= )
{
DisJoinSet dis(n);
int per1;
int per2;
for(int i = ; i< m;i++)
{
int num = ;
cin>>num;
cin>>per1;
for(int i = ;i < num; i++)
{
cin>>per2;
dis.Union(per1,per2);
}
}
cout<<dis.GetAswer()<<endl;
}
return ;
}