题目链接：

题意：给你一系列形如u v的点对（u v代表一条由u指向v的有向边），请问由给你的点构成的图是不是一棵树？

树的特征：①每个节点（除了根结点）只有一个入度；②只有一个根结点。

 

题解：用并查集合并点，对于一条边，如果连接的两点已经在同一并查集内，则可以直接判否。合并时按边的方向记录点的入度，如果某个点入度大于1也就是某个点有多个父亲节点，则说明不是树。合并时顺便记录合并总次数，最后合并点数-1次则是树。

 

代码：

#include 
     
      #include 
      
       const int MAX_SIZE = 105;int parent[MAX_SIZE];bool flag[MAX_SIZE];void make_set(){  //初始化	for(int x = 1; x < MAX_SIZE; x ++){		parent[x] = x;		flag[x] = false;	}}int find_set(int x){   //寻找根节点，带路径压缩	if(x != parent[x])		parent[x] = find_set(parent[x]);	return parent[x];}void union_set(int x, int y){  //合并	x = find_set(x);	y = find_set(y);	if(x == y) return;	parent[y] = x;}bool single_root(int n){   //判断是不是只有一个根，条件(1)	int i = 1;	while (i <= n && !flag[i]){		++i;	}	int root = find_set(i);	while (i <= n){		if (flag[i] && find_set(i) != root){			return false;		}		++i;	}	return true;}int main(){	int x, y;	bool is_tree = true;	int range = 0;	int idx = 1;	make_set();	while (scanf("%d %d", &x, &y) != EOF){		if (x < 0 || y < 0){			break;		}		if (x == 0 || y == 0){			if (is_tree && single_root(range)){				printf("Case %d is a tree.\n", idx++);			}			else{				printf("Case %d is not a tree.\n", idx++);			}			is_tree = true;			range = 0;			make_set();			continue;		}		if (!is_tree){			continue;		}		range = x > range ? x : range;		range = y > range ? y : range;		flag[x] = flag[y] = true;		if (find_set(x) == find_set(y)){  //如果两者属于一个集合（也就是有共同祖先），并且两者还有父子关系，那么无法形成树，条件2			is_tree = false;		}		union_set(x, y);	}	return 0;}