树

树的概念是

• 根的入度为0，其他入度为1
• 不能形成环
• 只有1个根

审题不规范，交题两行泪
我特么就少了个句号，wa了好久好久
然后把第一次提交的代码加了句号后，ac了

版本1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define bug printf("hh\n")
using namespace std;
const int maxn=1e5;
int fa[maxn],Rank[maxn],degree[maxn];
int flag=1;
int cnt=1;
std::vector<int> vec;
int father(int x){
    if(fa[x]==x)return x;
    return fa[x]=father(fa[x]);
}
void unit(int u,int v){//6和8
    int x=father(u);//x=6
    int y=father(v);//y=3
    if(Rank[x]<Rank[y])fa[x]=y;//rank[6]=1,rank[3]=0
    else{
        fa[y]=x;
        if(Rank[x]==Rank[y])Rank[x]++;
    }
}
void init(){
    for(int i=1;i<maxn;i++)fa[i]=i;
    memset(Rank,0,sizeof(Rank));
    memset(degree,0,sizeof(degree));
    flag=1;
    vec.clear();
}
void doit(){
    for(int i=1;i<vec.size();i++){
        if(father(fa[vec[i]])!=father(fa[vec[i-1]])){
            flag=0;
            return;
        }
        if(degree[vec[i]]>=2){
            flag=0;

            return;
        }
        //printf("%d %d\n",vec[i],degree[vec[i]]);
    }
}
void print(){
    printf("%s.\n",flag==1?"a tree":"not a tree");
}
int main(){
    int u,v;
    init();
    while(~scanf("%d%d",&u,&v)){
        if(u==0&&v==0){//数据输入到了0，表示一组完成，该开始计算且初始化
            printf("Case %d is ",cnt++);
            doit();
            print();
            init();
        }
        else if(u==-1&&v==-1){//退出情况
            break;
        }else {//合并且求数据的组数
            unit(u,v);
            degree[v]++;
            vec.push_back(u);
            vec.push_back(v);
        }
    }
    return 0;
}

版本2

/*
1.只有一个根
2.不能成环
3.除了根节点其他节点的入度为1
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
const int maxn=1e6+5;
int fa[maxn],degree[maxn];
int cnt=1;
bool flag=true;
set<int>s;
set<int>::iterator it;
int father(int x){//查找父节点
    return fa[x]==x?x:father(fa[x]);
}
void unit(int u,int v){//联合节点u和v
    int x=father(u);
    int y=father(v);
    if(x!=y)fa[y]=x;
    else flag=false;//成环了

}
void init(){//初始化
    flag=true;
    for(int i=0;i<maxn;i++){
        fa[i]=i;
        degree[i]=0;
    }
    s.clear();

}
void print(){//根据flag输出
    printf("Case %d is",cnt++);
    printf("%sa tree.\n",flag==true?" ":" not ");
}
bool root_check(){//唯一根
    int num=s.size();
    it=s.begin();
    int root=father(fa[*it]);
    for(;it!=s.end();it++){
        int t=father(fa[*it]);
        if(t!=root){
            flag=false;
            return false;
        }
    }
    return true;
}
void degree_check(){//入度
    if(root_check()){
        it=s.begin();
        int root=father(fa[*it]);
        if(degree[root]!=0){flag=false;return;}
        for(;it!=s.end();it++){
            int t=*it;
            if(t!=root&&degree[t]!=1){//对于非根节点入度不为1
                flag=false;
                return;
            }
        }
    }
}
void circle_check(){//环判断

}
bool check(){//

    degree_check();
    //circle_check();
}
int main(){
    int u,v;
    init();
    while(~scanf("%d%d",&u,&v)){
        if(u==-1&&v==-1)break;
        else if(u==0&&v==0){
            if(s.empty())flag=false;
            else if(flag==true)check();
            print();
            init();
        }else{
            unit(u,v);
            s.insert(u);
            s.insert(v);
            degree[v]++;
        }
    }
    return 0;
}