给出一系列节点对，判断是不是树。是树的条件是：只有一个根节点，没有指向根节点的边，除了根节点每个节点都只有一条（出度可以不是1，入度必须是1，根节点在最后给出）边指向它

第一个 第二个满足条件，第三个不满足，因为8节点入度为2

这道题很容易往并查集的方向上想，事实上用并查集也可以解决.但是这个问题有更加简单的解法,不需要使用并查集.

题目给出了有向边的数据，因为所有的顶点都是以有向边端点的形式给出的，所以不存在孤立的点.

如果所有的边能够构成一棵树，那么必然会有:顶点个数 = 边的数目 + 1，另外题目还要求不能有节点入度大于1，因此再加上判断入度是否都1的条件。

因此，只要满足根节点以外节点入度都为1并且nvertices = nedges + 1,就必然是一棵树.

#include<iostream>
#define MAX 50000
using namespace std;

int parent[MAX+1],a,b,nedges,nvertices;
bool visit[MAX+1];
int main()
{
int count = 1;
while(scanf("%d%d",&a,&b))
{
 if(a == -1 && b == -1)
 break;
 if(a == 0 && b == 0)
 {
  printf("Case %d is a tree.\n",count);
  count++;
  continue;
 }
       nvertices = 0,nedges = 0;
 bool flag = true;
 memset(parent,0,sizeof(parent));
 memset(visit,false,sizeof(visit));
 while( !(a == 0 && b == 0))
 {
  if(flag == true)
  {
   if(parent[b]>0)
   flag = false; 
   if(visit[a] == false)
   nvertices++,visit[a] = true;
   if(visit[b] == false)
   nvertices++,visit[b] = true;
   nedges++;
   parent[b]=a;
  }
  scanf("%d%d",&a,&b);        
 }
    if(nvertices == nedges + 1 && flag == true)
 printf("Case %d is a tree.\n",count);
 else
 printf("Case %d is not a tree.\n",count);
 count++;
}
}

用并查集解决：

总结一下，其实题目要求是就是确定一个边序列是否为树。入度只能为1也是确定是否为树，入度为2或者更多则为图。因此只需要判断既不是图也不是森林（两个或者更多独立的树存在）就可以了。之所以用并查集是因为可以迅速判断一对新来的边是否构成环（即图），因为他们与根节点直接相连，通过判断他们的根节点是否相同就可以判断是否存在环（这两个节点本身存在一条新边。）

#include<iostream>

using namespace std;

const int N = 105;

int p[N];

bool flag[N];

void make_set(void)

{

    for(int i = 0; i < 105; i++)

    {

        p[i] = i;

        flag[i] = false;

    }

}

int find_set(int x){

    return p[x] == x ? x : (p[x] = find_set(p[x]));

}

void union_set(int x, int y){

    x = find_set(x);

    y = find_set(y);

    if(x == y) return;

    p[y] = x;

}

int main(){

    int x, y, t = 1, first;

    while(scanf("%d %d", &x, &y) != EOF){

        if(x == -1 && y == -1) break;

        if(x == 0 && y == 0){        // 1.空树也是树，果断坑爹了

            printf("Case %d is a tree.\n", t ++);

            continue;

        }

        make_set();

        flag[x] = flag[y] = true;

        first = x;

        bool tree = true;

        if(x == y) tree = false;    //  两个数相等表示指向自己，不是树

        else union_set(x, y);

        while(scanf("%d %d", &x, &y) && x != 0){

            flag[x] = flag[y] = true;

            if(find_set(x) == find_set(y)) tree = false;   // 2.两个数的树根相同，现在又出现新边，构成环

            union_set(x, y);//合并

        }

        for(int i = 1; i < 105; i ++)   

//判断是否是森林，即每个已经出现的节点（flag=1）与任意的节点（first节点）是否在同一颗树上。

            if(flag[i] && find_set(i) != find_set(first)) {

                tree = false;

                break;

            }

        if(tree) printf("Case %d is a tree.\n", t ++);

        else printf("Case %d is not a tree.\n", t ++);

    }

    return 0;

}

UnionFind1308