题解 | #Is It A Tree?#

速度还行

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 10000 + 10;

int Find(int x, int* parent){
	if(*(parent+x) < 0){
		return x;
	}else{
		return Find(*(parent+x), parent);
	}
}

//不能二父，不能形成闭环 

bool Union(int x, int y, int* parent){//本题不同之处：只能x作为y父 
	if(*(parent+y) == x){//重复边，在这题好像也算寄 
		return false;
	}else if(*(parent+y) > 0){//二父，“不是树” 
		return false;
	}else{//做连接操作 
		*(parent+y) = x;
	}
	return true;
}

int main(){
	int x,y;
	int parent[MAXN];
	int tag = 0;
	int casenum = 1;
	memset(parent, -1, sizeof(parent));
	vector<int> v;//记录动用了哪些结点 
	while(scanf("%d%d",&x, &y) != EOF){
		if(x==-1 && y==-1){
			break;
		}
		while(!(x==0 && y==0)){
			v.push_back(x);
			v.push_back(y);
			if(!Union(x, y, parent)){
				tag = 1;
			}
			scanf("%d%d", &x, &y);
		}
		sort(v.begin(), v.end());
		int cnt = 0;
		for(int i=0; i<v.size(); i++){
			if(i>0 && v[i] == v[i-1]){
				continue;
			}
			if(parent[v[i]] < 0){
				cnt++;
				if(cnt > 1){//不连通
					tag = 1;
					break;
				}
			}
		}
		if(!cnt){//闭环
			tag = 1;
		}
		if(v.empty()){//空集
			tag = 0;
		}
		if(tag){
			printf("Case %d is not a tree.\n",casenum++);
		}else{
			printf("Case %d is a tree.\n",casenum++);
		}
		tag = 0;
		memset(parent, -1, sizeof(parent));
		v.clear();
	}
	return 0;
}