思考：首先对这道题目很无语，没有数据量。
注意一下几点：1. 空树2.仅有一个树根3森林的情况。
如果是一棵树则N个点，N-1条边（如果连通） 如果是森林则不连通。
同时满足连通且N个顶点有N-1条边。这个代码好烂！
#include#include #include #include #include using namespace std; const int maxn = 100000; // 10^6 Memory Limit Exceeded vector v[maxn+10]; bool vis[maxn+5]; int edge_num; int node_num; int travel_node; void dfs(int x) { if(!vis[x]) { travel_node++; vis[x] = true; } else return; for(int i = 0; i < (int)v[x].size(); i++) { dfs(v[x][i]); } } void init() { edge_num = 0; node_num = 0; for(int i = 0; i < maxn; i++) v[i].clear(); } int main() { bool ok = true; int index = 0; int start; // dfs from this point. while(ok) { init(); start = 0; int x, y; int a = 0, b = 0; while(scanf("%d%d", &x, &y) == 2 && (x || y)) { if(x < 0 && y < 0) {ok = false; break;} v[x].push_back(y); v[y].push_back(x); edge_num++; if(!start) start = x; if(a==0 && b==0) { a = x; b = y; } } if(!ok) break; if(x==0 && y==0 && a == 0 && b == 0) { //0 0 printf("Case %d is a tree.\n", ++index); continue; } for(int i = 1; i < maxn; i++) { if(v[i].size()) node_num++; } if(edge_num+1 == node_num); // exist ring. else { printf("Case %d is not a tree.\n", ++index); continue; } // whether the tree is connected memset(vis, false, sizeof(vis)); travel_node = 0; dfs(start); if(travel_node == node_num) { printf("Case %d is a tree.\n", ++index); } else { printf("Case %d is not a tree.\n", ++index); } } return 0; }