#判断图是否是树#并查集#北京大学复试

https://www.acwing.com/problem/content/3412/

思路：本题需要判断一个图是否为树，这需要我们判断三个要素：

1.一个树的边数应该比节点数少1

2.一个树的节点入度应该小于等于2，且只有一个入度为0的节点即根节点

3.从根节点到任意节点有且仅有一条唯一路线

1我们使用两个计数变量edgecount和vertexcount解决，2我们用入度数组和访问数组解决，3我们用并查集解决，并维护一个布尔型变量记录当前是否判断可以成树

注意点：1.每次完成后需要将数组变量进行初始化防止影响下一步2.将布尔型变量修改后不需要return而是应该继续循环直到所有数据都处理完成

/*树是一种众所周知的数据结构，它既可以是空的（null），也可以是一个节点或多个节点的集合，这些节点通过有向边连接且满足以下属性。
有且仅有一个节点，我们称之为根节点，没有任何有向边指向该节点。
除了根节点外，每个节点都有且仅有一条指向它的边。
从根节点到每个其他节点都有一条唯一的有向边序列。
给定若干个由有向边连接的节点集合的描述，请确定它们是否满足树的定义。
输入格式
输入包含多组测试数据。每组数据占若干行，包含若干个对于有向边的描述，每个有向边的描述包含两个整数 a和 b，
 表示这条有向边从节点 a指向节点 b。当出现数对 0 0 时，表示这组数据的输入结束。当出现数对 -1 -1 时，表示全部输入结束。
输出格式：每个数据输出占一行，表示结果。格式为 Case k is a tree. 或 Case k is not a tree.，其中 k为组别编号，从 1开始。
数据范围0<a,b<10000,每个输入最多包含 100 组数据。
输入样例
6 8  5 3  5 2  6 4
5 6  0 0*/
#include <bits/stdc++.h>

using namespace std;
int father[10001];
void initialize(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}

int findele(int u) {
    if (u == father[u]) { //节点的下标与数组值相等，即为找到了根节点
        return u;
    } else {
        father[u]=findele(father[u]);//继续向上找
        return father[u];
    }
}
void Unionele(int i, int j) {
    int uroot;
    uroot = findele(i);
    int vroot;
    vroot = findele(j);
    father[vroot] = uroot;
}

int main() {
    int u,v;
    initialize(10001);
    int edgeCount = 0;//边数
    int vertexCount = 0;//顶点数
    vector<int> vertex(10001); // vertex[i] -> 0 说明 i 未出现过
    vector<int> inDegree(10001); // inDegree[i] 记录i的入度
    bool isOK = true;
    int caseIdx = 1;
    while(1){
        scanf("%d%d",&u,&v);
        if(u==-1&&v==-1){ //整个输出结束
            break;
        }
        else if(u==0&&v==0){ //单次输出结束
            if(vertexCount!=edgeCount+1){
                isOK = false;
            }
            if(vertexCount == 0&&edgeCount == 0){
                isOK = true;
            }
            if(isOK == true){
                printf("Case %d is a tree.\n",caseIdx);
            }
            else{
                printf("Case %d is not a tree.\n",caseIdx);
            }
            initialize(10001);
            edgeCount=0;
            vertexCount = 0;
            for (int i = 0; i < 10001; ++i) {
                vertex[i] = 0;
                inDegree[i] = 0;
            }
            isOK = true;
            ++caseIdx;
        }
        else{//继续输入
            edgeCount++;
            if(vertex[u] == 0){
                vertex[u] = 1;
                ++vertexCount;
            }
            if(vertex[v]==0){
                vertex[v] = 1;
                ++vertexCount;
            }
            if(findele(v)== findele(u)){
                isOK = false;
            }
            else{
                Unionele(u,v);
            }
            ++inDegree[v];
            if(inDegree[v]>=2){
                isOK = false;
            }
        }
    }
    return 0;
}