题目地址：The Suspects
题目大意：
大家都知道SARS病毒的传播在2003年 的中期传播的十分骇人，这个题就是关于SRAS的传播问题，题目意思有一群人每个人的编号0->n-1。其中0为SARS病毒的携带者，然而他们每个人都可能加入了多个组织，每个组织中如果有一个病毒携带者，我们就认为整个组织所有人都是携带病毒的危险人员。让你编一个程序判断一共有多少个危险人员。
解题思路：
简单并查集。
代码：
1 #include <algorithm> 2 #include <iostream> 3 #include <sstream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <string> 8 #include <bitset> 9 #include <vector> 10 #include <queue> 11 #include <stack> 12 #include <cmath> 13 #include <list> 14 //#include <map> 15 #include <set> 16 using namespace std; 17 /***************************************/ 18 #define ll long long 19 #define int64 __int64 20 /***************************************/ 21 const int INF = 0x7f7f7f7f; 22 const double eps = 1e-8; 23 const double PIE=acos(-1.0); 24 const int d1x[]= {-1,1,0,0}; 25 const int d1y[]= {0,0,-1,1}; 26 const int d2x[]= {0,-1,0,1}; 27 const int d2y[]= {1,0,-1,0}; 28 const int fx[]= {-1,-1,-1,0,0,1,1,1}; 29 const int fy[]= {-1,0,1,-1,1,-1,0,1}; 30 /***************************************/ 31 void openfile() 32 { 33 freopen("data.in","rb",stdin); 34 freopen("data.out","wb",stdout); 35 } 36 /**********************华丽丽的分割线,以上为模板部分*****************/ 37 int father[30005]; 38 void makeset(int i) 39 { 40 father[i]=i; 41 } 42 int find(int x) 43 { 44 if (x!=father[x]) 45 { 46 father[x]=find(father[x]); 47 return father[x]; 48 } 49 return x; 50 } 51 void unionone(int a,int b) 52 { 53 int x;int y; 54 x=find(a); 55 y=find(b); 56 father[x]=y; 57 } 58 int main() 59 { 60 int n,m; 61 while(scanf("%d%d",&n,&m)&&(n+m)) 62 { 63 int l; 64 int i,j; 65 int a[30005]; 66 for(i=0;i<n;i++) 67 makeset(i); 68 for(i=0;i<m;i++) 69 { 70 scanf("%d",&l); 71 for(j=0;j<l;j++) 72 { 73 scanf("%d",&a[j]); 74 } 75 for(j=1;j<l;j++) 76 { 77 unionone(a[j],a[j-1]); 78 } 79 } 80 int sum=0; 81 for(i=0;i<n;i++) 82 if (find(0)==find(i)) 83 sum++; 84 printf("%d ",sum); 85 } 86 return 0; 87 }