杭电1856（More is better)

这个题主要有个小细节就是n=0时，应该输出1；这里给出两种方法:

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<stdlib.h>
 4 #define N 10000005
 5 int set[N],b[100005];
 6 int a[100005];
 7 int s[100005];
 8 int find(int x)
 9 {
10     if(x==set[x])
11         return x;
12     else
13         set[x]=find(set[x]);
14 }
15 int main()
16 {
17     int n,m,x,y,f1,f2;
18     int i,j,k;
19     while(scanf("%d",&n)!=-1)
20     {
21         if(n==0)
22         {
23             printf("1\n");//至关重要
24             continue;
25         }
26         for(i=1;i<N;i++)
27             set[i]=i;
28         m=0;
29         for(i=1;i<=n;i++)
30         {
31             scanf("%d%d",&x,&y);
32             if(x>m)m=x;
33             if(y>m)m=y;
34             f1=find(x);
35             f2=find(y);
36             if(f1!=f2)
37                 set[f1]=f2;
38         }
39         memset(b,0,sizeof(b));
40         k=0;
41         int p,c;
42         c=0;
43         for(i=1;i<=m;i++)
44         {
45             if(set[i]==i)
46             {
47                 a[k++]=i;
48             }
49         }
50         
51         memset(s,0,sizeof(s));
52          for(i=1;i<=m;i++)
53          {
54              for(j=0;j<k;j++)
55              {
56                  if(find(i)==find(a[j]))
57                      s[a[j]]++;
58              }
59          }
60         int max=-1;
61         for(i=0;i<k;i++)
62             if(max<s[a[i]])
63                 max=s[a[i]];
64             printf("%d\n",max);
65     }
66     return 0;
67 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 10000005
 4 int max,set[N],mark[N];
 5 void met()
 6 {
 7     int i;
 8     for(i=0;i<N;i++)
 9     {
10         set[i]=i;
11         mark[i]=1;
12     }
13 }
14 int find(int x)
15 {
16     if(x!=set[x])
17         set[x]=find(set[x]);
18     return set[x];
19 }
20 void power(int a,int b)
21 {
22     int x=find(a);
23     int y=find(b);
24     if(x==y)
25         return;
26     if(mark[x]>=mark[y])
27     {
28         set[y]=x;
29         mark[x]+=mark[y];
30         if(mark[x]>max)
31             max=mark[x];
32     }
33     else
34     {
35         set[x]=y;
36         mark[y]+=mark[x];
37         if(max<mark[y])
38             max=mark[y];
39     }
40 }
41 int main()
42 {
43     int n;
44     while(scanf("%d",&n)!=-1)
45     {
46         if(n==0)
47         {
48             printf("1\n");
49             continue;
50         }
51         met();
52         max=0;
53         int a,b;
54         while(n--)
55         {
56             scanf("%d%d",&a,&b);
57             power(a,b);
58         }
59         printf("%d\n",max);
60     }
61     return 0;
62 }