先来个最水的
poj 2524 Ubiquitous Religions
http://poj.org/problem?id=2524
【题意】：给出n个大学生，其中有m对宗教信仰相同的学生，请你估算这n个学生中最多有多少种宗教信仰。
【思路】： 先设 答案为n 每合并一个集合减一就ok了
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 using namespace std; 6 7 8 int n; 9 int f[50002]; 10 11 void init() 12 { 13 for(int i=0;i<=n;i++) 14 f[i]=i; 15 16 } 17 18 19 int find(int x) 20 { 21 return f[x]==x?x:f[x]=find(f[x]); 22 } 23 24 int main() 25 { 26 int i,j,a,b,m,p=1; 27 while(scanf("%d%d",&n,&m)) 28 { 29 if(n==0&&m==0) 30 break; 31 init(); 32 int ans=n; 33 while(m--) 34 { 35 scanf("%d%d",&a,&b); 36 int aa,bb; 37 aa=find(a); 38 bb=find(b); 39 if(aa!=bb) 40 { 41 f[aa]=bb; 42 ans--; 43 } 44 } 45 printf("Case %d: %d\n",p++,ans); 46 } 47 48 return 0; 49 }
poj 1611 The Suspects
http://poj.org/problem?id=1611
【题意】：N个组的学生，一个学生能同时加入不同的组，同一组的学生会同时感染病毒，现在0号的学生感染了病毒，问一共有多少个人感染病毒。
【思路】 并查集 若是两个 学生在的集合不同（根节点不同）就 合并 只要把一个根节点变成另一个根节点的father 同时新的根节点的 sum值 为两集合之和 就好了 在find x的时候 ，找根节点的同时更新sum[x]的值 （从离根最近的开始）
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 int f[30002],sum[30002],n; 6 7 void init() 8 { 9 for(int i=0;i<=n;i++) 10 { 11 sum[i]=1;f[i]=i; 12 } 13 } 14 15 int find(int x) 16 { 17 if(f[x]==x) 18 return x; 19 f[x]=find(f[x]); 20 sum[x]=sum[f[x]]; 21 return f[x]; 22 } 23 24 void lian(int tx,int ty) 25 { 26 f[ty]=tx; 27 sum[tx]+=sum[ty]; 28 } 29 30 int main() 31 { 32 int i,j,m,t,num,a,b; 33 while(~scanf("%d%d",&n,&m)) 34 { 35 if(n==0&&m==0) 36 break; 37 init(); 38 while(m--) 39 { 40 scanf("%d",&num); 41 scanf("%d",&a); 42 num--; 43 while(num--) 44 { 45 scanf("%d",&b); 46 int aa,bb; 47 aa=find(a); 48 bb=find(b); 49 if(aa!=bb) 50 lian(aa,bb); 51 } 52 } 53 printf("%d\n",sum[find(0)]); 54 } 55 }
poj 1703
【题意】 有两个帮派，现在告诉你一些互相敌对的点对，然后让你判断某两个点之间的关系
【思路】只要 每个节点 多设一项 kind 表示和根节点的关系是相同还是不同 相同为0 不同为1 输入敌对的 关系时
1 #include<iostream> 2 #include<stdio.h> 3 using namespace std; 4 5 struct node{int kind; int fa;}no[100002]; 6 int n; 7 8 void init() 9 { 10 for(int i=0;i<=n;i++) 11 { 12 no[i].fa=i; no[i].kind=0; 13 } 14 } 15 16 int find(int x) 17 { 18 if(no[x].fa==x) 19 return x; 20 int t; 21 t=find(no[x].fa) 22 // 这里执行完 x.fa 的fa和kind都求出来了 fa是 这个集合的根节点 kind是x.fa与根节点的关系 23 // 而此时 x.fa 和x.kind 都未更新 下面就是 根据 x与x.fa的关系和 x.fa与根节点的关系 推出 x与根节点的关系 24 no[x].kind^=no[no[x].fa].kind; 25 return no[x].fa=t; 26 } 27 28 int main() 29 { 30 int i,j,m,t,a,b; 31 char c[10]; 32 scanf("%d",&t); 33 while(t--) 34 { 35 36 scanf("%d%d",&n,&m); 37 init(); 38 while(m--) 39 { 40 scanf("%s%d%d",c,&a,&b); 41 int aa,bb; 42 aa=find(a); 43 bb=find(b); 44 if(c[0]==‘D‘) 45 { 46 no[aa].fa=bb; 47 no[aa].kind=no[a].kind^no[b].kind^1;//aa与 bb 的关系 有a与aa的关系 和b与bb的关系推出 48 } 49 else 50 { 51 if(aa!=bb) 52 printf("Not sure yet.\n"); 53 else 54 { 55 if(no[a].kind==no[b].kind) 56 printf("In the same gang.\n"); 57 else 58 printf("In different gangs.\n"); 59 } 60 } 61 } 62 } 63 }
poj 1988 Cube Stacking
http://poj.org/problem?id=1988
【题意】 有n个元素，开始每个元素自己一栈，有两种操作，将含有元素x的栈放在含有y的栈的顶端，合并为一个栈。第二种操作是询问含有x元素下面有多少个元素。
【思路】每个节点除了一项fa 还增加一项d 和一项 sum的表示的是这个节点下面的元素个数 也就是所求。 sum表示的是这个节点所在的集合的节点数
根节点的d值总是0 。
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 6 struct node{int fa;int sum;int d;} no[30002]; 7 8 9 10 int find(int x) 11 { 12 if(no[x].fa==x) 13 return x; 14 int t; 15 t=find(no[x].fa); 16 no[x].d+=no[no[x].fa].d; 17 return no[x].fa=t; 18 } 19 20 void merge(int tx,int ty) 21 { 22 no[tx].fa=ty; 23 no[tx].d=no[ty].sum; 24 no[ty].sum+=no[tx].sum; 25 26 } 27 28 void init() 29 { 30 for(int i = 0;i <= 30000;i++) 31 { 32 no[i].fa = i; 33 no[i].sum=1; 34 no[i].d=0; 35 } 36 } 37 38 int main() 39 { 40 int a,b,aa,bb,n; 41 char c[10]; 42 while(scanf("%d",&n) != EOF) 43 { 44 init(); 45 46 for(int i = 0;i < n;i++) 47 { 48 scanf("%s",c); 49 if(c[0]==‘M‘) 50 { 51 scanf("%d%d",&a,&b); 52 aa=find(a); 53 bb=find(b); 54 if(aa!=bb) 55 merge(aa,bb); 56 find(a); 57 } 58 if(c[0]==‘C‘) 59 { 60 scanf("%d",&a); 61 find(a); 62 printf("%d\n",no[a].d); 63 } 64 } 65 } 66 return 0; 67 }