1 //0 0涔熸槸鏍?br> 2 //鏈変笖鍙湁涓涓《鐐瑰叆搴︿負0錛屽叾瀹冮《鐐瑰叆搴﹀繀欏諱負涓
3 #include<iostream>
4 using namespace std;
5 int in[100];
6 int hash[1000];
7 bool visit[1000];
8 int main()
9 {
10 int a,b,cas=1;
11 while(scanf("%d%d",&a,&b)&&a>=0&&b>=0)
12 {
13 memset(visit,0,sizeof(visit));
14 memset(hash,0,sizeof(hash));
15 memset(in,0,sizeof(in));
16 if(a==0&&b==0)
17 {
18 printf("Case %d is a tree.\n",cas++);
19 continue;
20 }
21 int m=1;
22 hash[++hash[0]]=a;
23 visit[a]=visit[b]=1;
24 hash[++hash[0]]=b;
25 in[b]++;
26 bool flag=0;
27 while(scanf("%d%d",&a,&b)&&a&&b)
28 {
29 ++m;
30 if(!visit[a])
31 hash[++hash[0]]=a;
32 if(!visit[b])
33 hash[++hash[0]]=b;
34 visit[a]=visit[b]=1;
35 if(++in[b]>1)
36 {
37 flag=1;
38 printf("Case %d is not a tree.\n",cas++);
39 }
40 }
41 if(flag)continue;
42 else
43 {
44 if(hash[0]-1!=m)
45 {
46 printf("Case %d is not a tree.\n",cas++);
47 continue;
48 }
49 int root;
50 bool flag=1;
51 for(int i=1;i<=hash[0];++i)
52 if(in[hash[i]]==0)
53 {
54 flag=0;
55 root=i;
56 break;
57 }
58 if(flag)
59 {
60 printf("Case %d is not a tree.\n",cas++);
61 continue;
62 }
63 for(int i=1;i<=hash[0];++i)
64 if(i!=root&&in[hash[i]]!=1)
65 {
66 printf("Case %d is not a tree.\n",cas++);
67 continue;
68 }
69 printf("Case %d is a tree.\n",cas++);
70 }
71 }
72 return 0;
73 }
3 #include<iostream>
4 using namespace std;
5 int in[100];
6 int hash[1000];
7 bool visit[1000];
8 int main()
9 {
10 int a,b,cas=1;
11 while(scanf("%d%d",&a,&b)&&a>=0&&b>=0)
12 {
13 memset(visit,0,sizeof(visit));
14 memset(hash,0,sizeof(hash));
15 memset(in,0,sizeof(in));
16 if(a==0&&b==0)
17 {
18 printf("Case %d is a tree.\n",cas++);
19 continue;
20 }
21 int m=1;
22 hash[++hash[0]]=a;
23 visit[a]=visit[b]=1;
24 hash[++hash[0]]=b;
25 in[b]++;
26 bool flag=0;
27 while(scanf("%d%d",&a,&b)&&a&&b)
28 {
29 ++m;
30 if(!visit[a])
31 hash[++hash[0]]=a;
32 if(!visit[b])
33 hash[++hash[0]]=b;
34 visit[a]=visit[b]=1;
35 if(++in[b]>1)
36 {
37 flag=1;
38 printf("Case %d is not a tree.\n",cas++);
39 }
40 }
41 if(flag)continue;
42 else
43 {
44 if(hash[0]-1!=m)
45 {
46 printf("Case %d is not a tree.\n",cas++);
47 continue;
48 }
49 int root;
50 bool flag=1;
51 for(int i=1;i<=hash[0];++i)
52 if(in[hash[i]]==0)
53 {
54 flag=0;
55 root=i;
56 break;
57 }
58 if(flag)
59 {
60 printf("Case %d is not a tree.\n",cas++);
61 continue;
62 }
63 for(int i=1;i<=hash[0];++i)
64 if(i!=root&&in[hash[i]]!=1)
65 {
66 printf("Case %d is not a tree.\n",cas++);
67 continue;
68 }
69 printf("Case %d is a tree.\n",cas++);
70 }
71 }
72 return 0;
73 }
]]>
澧炲姞榪炰釜浜岀淮鏁扮粍
涓涓〃紺轟粠璧風偣鍒板綋鍓嶇偣鎵闇鐨勯儴鏁?br>鍙︿竴涓〃紺哄埌杈懼綋鍓嶇殑鏈灝忚礬寰勬暟
濡傛灉
褰撳墠鐐規鏁?1==涓嬩釜鐐圭殑姝ユ暟
閭ｄ箞涓嬩釜鐐圭殑鏈灝忚礬寰勬暟+=褰撳墠鐐圭殑鏈灝忚礬寰勬暟
榪欐牱鍋氬氨涓嶄細瓚呮椂浜嗭紝閫熷害寰堝揩
]]>
2 using namespace std;
3 int n,m;
4 int d[101][101];
5 int main()
6 {
7 int a,b;
8 while(scanf("%d",&n)&&n)
9 {
10 //鐢╩emset鏃犳硶璧嬪糏NT_MAX
11 for (int i=1;i<=n;++i)
12 for(int j=1;j<=n;++j)
13 d[i][j]=INT_MAX;
14 for(int i=1;i<=n;++i)
15 {
16 scanf("%d",&m);
17 for(int j=1;j<=m;++j)
18 {
19 scanf("%d%d",&a,&b);
20 d[i][a]=b;
21 }
22 }
23 for(int k=1;k<=n;++k)
24 for(int i=1;i<=n;++i)
25 for(int j=1;j<=n;++j)
26 if(d[i][k]<INT_MAX&&d[k][j]<INT_MAX&&d[i][j]>d[i][k]+d[k][j])
27 d[i][j]=d[i][k]+d[k][j];
28 int Max;
29 int Min=INT_MAX;
30 int point=-1;
31 bool connect;
32 for(int i=1;i<=n;++i)
33 {
34 connect=1;
35 Max=-1;
36 for(int j=1;j<=n;++j)
37 if(i!=j)
38 {
39 if(d[i][j]==INT_MAX)
40 {
41 connect=0;
42 break;
43 }
44 Max=max(Max,d[i][j]);
45 }
46 if(connect&&Max<Min)
47 {
48 Min=Max;
49 point=i;
50 }
51 }
52 if(point==-1)printf("disjoint\n");
53 else printf("%d %d\n",point,Min);
54 }
55 return 0;
56 }
]]>
4 //zoj2833
5 #include <iostream>
6 using namespace std;
7 int n,m;
8 int father[100000+1];
9 int f[100000+1];//鏈嬪弸鐨勪釜鏁?/span>
10 int rank[100000+1];
11 void make_set(int s)
12 {
13 for(int i=1;i<=s;++i)
14 {
15 f[i]=1;
16 father[i]=i;
17 rank[i]=0;
18 }
19 }
20 int find_set(int x)
21 {
22 if(x!=father[x])
23 father[x]=find_set(father[x]);
24 return father[x];
25 }
26 void union_set(int x,int y)
27 {
28 int a=find_set(x);
29 int b=find_set(y);
30 if(rank[a]>rank[b])
31 {
32 father[b]=a;
33 f[a]+=f[b];
34 }
35 else
36 {
37 father[a]=b;
38 f[b]+=f[a];
39 }
40 if(rank[a]==rank[b])rank[b]++;
41 }
42
43 int main()
44 {
45 int a,b;
46 char tmp;
47 int cas=0;
48 while(scanf("%d%d",&n,&m)!=EOF)
49 {
50 if(cas)printf("\n");
51 printf("Case %d:\n",++cas);
52 make_set(n);
53 getchar();
54 for(int i=1;i<=m;++i)
55 {
56 tmp=getchar();
57 if(tmp=='M')
58 {
59 scanf("%d%d",&a,&b);
60 if(find_set(a)!=find_set(b))
61 union_set(a,b);
62 }
63 if(tmp=='Q')
64 {
65 scanf("%d",&a);
66 int sum=f[find_set(a)];
67 printf("%d\n",sum);
68 }
69 getchar();
70 }
71 }
72 return 0;
73 }
74
]]>