题解 | #Is It A Tree?#

首先这道题很容易想到并查集，但是需要注意的是，树的节点之间有一定的关系，即双亲、孩子，但是对于这道题来说无需那么清楚的搞清他们的关系，只需要判断是不是树就可以了。因为一棵树，只有根节点入度为0，其余的点入度为1，如果你发现有某些点的入度高于1，那么它肯定不是一棵树。下面结合代码分析。

#include<cstdio>
using namespace std;

const int MAXN=10000;

int Node[MAXN];
int indegree[MAXN];
bool visit[MAXN];   //这个标记数组主要的用途是提高效率，忽略没有出现的节点

void Init(){   //这里的并查集Node利用数组来表示，初始化均为-1表示每个节点均为孤立的根
	for(int i=1;i<MAXN;i++){
		indegree[i]=0;
		Node[i]=-1;
		visit[i]=false;
	}
}

int Find(int x){
	while(Node[x]>=0)
		x=Node[x];
	return x;
}

void Union(int r1,int r2){ //这里的Union采用如下思想:如果元素为负数，则索引值代表的节点即为根，
						   //其绝对值为子树的节点总数。
	if(r1==r2)return;
	else{
		if(Node[r1]<Node[r2]){  //如果Node[r1]<Node[r2]说明r1这个根节点所含节点数要多于r2这个点，
        						//那么应该将r2这棵树并入r1
			Node[r1]+=Node[r2];
			Node[r2]=r1;
		}
		else if(Node[r1]>Node[r2]){
			Node[r2]+=Node[r1];
			Node[r1]=r2;
		}
		else{
			Node[r1]+=Node[r2];
			Node[r2]=r1;
		}
	}
}

bool istree(){
	int component=0;
	int root=0;
	bool flag=true;
	for(int i=1;i<MAXN;i++){
		if(!visit[i])    //请注意这里的if-else的搭配顺序，
			continue;
		**if(Node[i]<0)**{ //如果加粗的这两个判断你是用else if那么会发生错误，因为一旦某一个满足，
        					//另一个就不会执行了，那么如果你继续分析下面的语句就会发现逻辑漏洞。
			component++;
		}
		**if(indegree[i]==0)**  //显然这里的if-else if才是正确的配对
			root++;
		else if(indegree[i]>1)
			flag=false;
	}
	if(component!=1 || root!=1)  //一旦有多个连通分量或者有多个根，那么它肯定不是一棵树
		flag=false;
	if(component==0 && root==0)
		flag=true;

	return flag;
}

int main(){
	int c=1;
	int a,b;
	Init();
	while(scanf("%d %d",&a,&b)!=EOF){
		if(a==-1 && b==-1)
			break;
		if(a==0 && b==0){
			if(istree())
				printf("Case %d is a tree.\n",c++);
			else
				printf("Case %d is not a tree.\n",c++);
			Init();
		}
		else{
			int root1=Find(a);
			int root2=Find(b);
			Union(root1,root2);
			indegree[b]++;
			visit[a]=true;  //对于出现过的点我们对它进行标记，后续只需要对这些出现过的点进行判断即可
			visit[b]=true;
		}
	}
}