POJ1038 Is It A Tree?

思考：首先對這道題目很無語，沒有數據量。

注意一下幾點：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;
}