http://acm.split.hdu.edu.cn/showproblem.php?pid=1325
1 #include<stdio.h>
2 #include<algorithm>
3 #include<string.h>
4 #include<iostream>
5 using namespace std;
6 const int M=100010;
7 int fa[M],vis[M],root[M];
8 int fin(int x){
9 return fa[x]==x?fa[x]:fa[x]=fin(fa[x]);
10 }
11 int unin(int x,int y){
12 return fa[fin(y)]=fin(x);
13 }
14 void init(int n){
15 for(int i=0;i<n;i++){
16 fa[i]=i;
17 }
18 memset(vis,0,sizeof(vis));
19 memset(root,0,sizeof(root));
20 }
21 int main()
22 {
23 int a,b;
24 int cas=1;int flag=1;
25 init(M);
26 while(~scanf("%d%d",&a,&b)){
27 if(a<0||b<0)break;
28
29
30 if(a==0&&b==0){
31 int k=0;
32 for(int i=1;i<M;i++){
33 if(vis[i]&&fa[i]==i){
34 k++;
35 }
36 if(root[i]>1){
37 flag=0;
38 break;
39
40 }
41
42 }
43 if(k>1)flag=0;
44 if(flag)printf("Case %d is a tree.
",cas++);
45 else printf("Case %d is not a tree.
",cas++);
46 flag=1;
47 init(M);
48 continue;
49 }
50 if(a!=b&&fin(a)==fin(b)){
51 flag=0;
52 }
53 else {
54 vis[a]=1;
55 vis[b]=1;
56 root[b]++;
57 unin(a,b);
58 }
59 }
60 return 0;
61 }
View Code对于这道题，主要是看图是否连通，而前面提到过在分析图是否连通的时候我们主要是看有几个根结点，而看有几个根节点又是看有几个fa[i]==i。
至于题目中说到的值可以有一种方法到达每一个节点，则是要看每个节点的入度情况，当出现有一个节点的入度大于1的话肯定就是NO
还可以发现，结点数一定小于边数-1，然后再判断有几个根结点也可以解出这道题，但是我们在这里主要运用并查集的知识