根据题目所给的3个不符合情况的条件，一个个判断图是否符合这3个条件即可
1.不能出现内部环，拓扑排序判断
2.不能有超过1个点的入度为0，因为只有一个树根
3.每个点最多一个入度
这里要注意的一点是这个点的数字是乱给的，所以最大值为8，但实际上不一定有8个点，这里记录一个最大值的参数，和一个总共点数的参数来进行判断即可
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 using namespace std; 5 6 const int N = 100005; 7 int in[N] , first[N] , k , maxn , del , sum;//maxn记录总共的点的个数，del记录删除了的点的个数 8 9 struct Edge{ 10 int y , next; 11 }e[N<<2]; 12 13 void add_edge(int x , int y ) 14 { 15 e[k].y = y , e[k].next = first[x]; 16 first[x] = k++; 17 } 18 19 void tuopu(int src) 20 { 21 del++; 22 for(int i = first[src] ; i!=-1 ; i=e[i].next){ 23 int v = e[i].y; 24 in[v]--; 25 if(!in[v]) tuopu(v); 26 } 27 } 28 29 int main() 30 { 31 // freopen("a.in" , "r" , stdin); 32 int x , y , cas = 0; 33 while(~scanf("%d%d" , &x , &y)){ 34 if(x < 0 && y < 0) break; 35 36 memset(first , -1 , sizeof(first)); 37 memset(in , -1 , sizeof(in)); 38 k = 0 , maxn = 0 , sum = 0;//sum表示总共点的个数 39 int cnt = 0 , root , flag = 0; //cnt记录有多少节点可以作为顶点了,flag作为判断是否有点超过1个入度 40 while(x != 0 || y!=0){ 41 add_edge(x , y); 42 maxn = max(max(maxn , x) , y); 43 if(in[x] < 0) in[x] = 0 , sum++; 44 if(in[y] < 0) in[y] = 0 , sum++; 45 in[y]++; 46 if(in[y] >= 2){ 47 flag = 1; 48 } 49 scanf("%d%d" , &x , &y); 50 } 51 // cout<<"maxn: "<<maxn<<endl; 52 if(flag){ 53 // cout<<"有点超过两个入度 "<<endl; 54 printf("Case %d is not a tree. " , ++cas); 55 continue; 56 } 57 for(int i = 1 ; i<=maxn ; i++) 58 if(!in[i]){ 59 root = i; 60 cnt++; 61 if(cnt>=2) break; 62 } 63 if(cnt >= 2){ 64 // cout<<"有超过两个点可作为树根 "<<endl; 65 printf("Case %d is not a tree. " , ++cas); 66 continue; 67 } 68 del = 0; 69 tuopu(root); 70 if(del < sum) 71 { 72 // cout<<"出现内部环 "<<endl; 73 printf("Case %d is not a tree. " , ++cas); 74 } 75 else 76 printf("Case %d is a tree. " , ++cas); 77 } 78 return 0; 79 }