http://acm.split.hdu.edu.cn/showproblem.php?pid=1856
对于这道题，主要就是让你求出有最多结点的树的树叶；
我们只要利用并查集的知识吧所输入的数据连接成树，然后逐一找出树叶最多的树就可以。利用一个num数组，在最开始的时候每个节点自己是一颗树，num[i]=1;在之后把在同一个父亲结点的num[i]连接起来。
再逐一查找出最大的就可以啦。
思路就是这样啊，可是我的提交上就是wa，心灰意冷啊，啊，啊啊，啊啊啊。我把我的代码贴上面，希望大神们看见帮我改一改。
1 #include<stdio.h> 2 #include<string.h> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 const int M=10000000; 7 int fa[M],num[M]; 8 void init(){ 9 for(int i=1;i<=M;i++){ 10 fa[i]=i; 11 num[i]=1; 12 } 13 } 14 int fin(int x){ 15 return fa[x]=x?fa[x]:fa[x]=fin(fa[x]); 16 } 17 void unin(int x,int y){ 18 int p=fin(x); 19 int q=fin(y); 20 if(p!=q){ 21 fa[p]=q; 22 num[q]+=num[p]; 23 } 24 } 25 int main() 26 { 27 int n,a,b; 28 while(~scanf("%d",&n)){ 29 if(n==0){ 30 printf("1 "); 31 continue; 32 } 33 int ans=0; 34 init(); 35 for(int i=0;i<n;i++){ 36 scanf("%d%d",&a,&b); 37 if(a>ans)ans=a; 38 if(b>ans)ans=b; 39 unin(a,b); 40 41 } 42 int maxn=0; 43 for(int i=1;i<=ans;i++){ 44 if(num[i]>maxn) 45 maxn=num[i]; 46 } 47 cout<<maxn<<endl; 48 } 49 return 0; 50 }
下面的这个是我在网上查找的大神的代码，我俩除啦参数之外是一样一样的啊，我的咋就不过呢。。。。。
1 #include<stdio.h> 2 #define N 10000000 3 int father[N],num[N]; 4 void initial()/*初始化*/ 5 { 6 int i; 7 for(i=1;i<=N;i++) 8 { 9 father[i]=i; 10 num[i]=1;/*开始时数量都为1，根节点为自己*/ 11 } 12 } 13 int find(int x) /*寻找根节点*/ 14 { 15 if(father[x]!=x) 16 father[x]=find(father[x]); 17 return father[x]; 18 } 19 void merge(int a,int b)/*合并a和b*/ 20 { 21 int p=find(a); 22 int q=find(b); 23 if(p!=q) 24 { 25 father[p]=q; 26 num[q]+=num[p];/*合并集合中元素个数*/ 27 } 28 } 29 int main() 30 { 31 int n,a,b,i,sum,max; 32 while(~scanf("%d",&n)) 33 { 34 if(n==0) 35 { 36 printf("1 "); 37 continue; 38 } 39 max=0; 40 initial(); /*初始化*/ 41 for(i=0;i<n;i++) 42 { 43 scanf("%d%d",&a,&b); 44 if(a>max) 45 max=a; 46 if(b>max) 47 max=b; 48 merge(a,b); /*合并集合*/ 49 } 50 int Max=0; 51 for(i=1;i<=max;i++) 52 if(num[i]>Max) /*查找最大值*/ 53 Max=num[i]; 54 printf("%d ",Max); 55 } 56 return 0; 57 }