POJ1308(Is It A Tree?)

链接：https://vjudge.net/problem/POJ-1308
思路：放在并查集专题的，思路是每次合并两个点，如果之前已经合并过了那么一定不能构成一棵树，完成之后检查集合的个数是否为1(即图是否连通)。我这题就想换一个写法，没想到关于树的东西还是一直写不好，到处wa，细节抠不好，所以写篇文章总结下坑点：
1、一定要注意空树、单个点、一条链等特殊情况
2、一定要注意是否需要判断图是否连通！（各大赛区已经有很多人栽在这同一个坑点上了）
3、注意是有向边还是无向边，有向边的树上dfs不需要加父节点判断，而无向边一般是需要的（对比这个专题的最后两个题）。
代码：

#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5+100;
int vis[maxn],mark[maxn];
vector<int> G[maxn];
int in[maxn];

int a,b;
int flag;

void dfs(int u){
    vis[u] = 1;
    for(int i=0;i<G[u].size();i++){
        int v = G[u][i];
        if(vis[v]){
            flag = 0;
            return;
        }
        dfs(v);
    }
}

int main(){
    int kase = 0;
    flag = 1;
    int maxv = 0;
    int times = 0;
    while(scanf("%d%d",&a,&b)){
        if((a==0&&b==0)||(a==-1&&b==-1)){
            if(a==-1)break;
            printf("Case %d ",++kase);
            if(times==0){//判断空树的情况（又被坑了！！！）
                printf("is a tree.\n");
                continue;
            }
            int num = 0;
            for(int i=1;i<=maxv;i++){//找入度为0的点的个数（根节点），不等于1则无解
                if(mark[i]&&!in[i])num++;
            }
            if(num!=1)flag = 0;
            else{
        for(int i=1;i<=maxv;i++){
            if(mark[i]&&in[i]==0){//找根节点做一次dfs，如果是树连通则一定可以遍历所有节点
                dfs(i);
                break;
            }
        }
        for(int i=1;i<=maxv;i++){
            if(mark[i]&&!vis[i])flag = 0;//如果有节点没有被遍历到（不连通），则无法构成树
        }
        }
        if(flag)printf("is a tree.\n");
        else printf("is not a tree.\n");
            for(int i=1;i<=maxv;i++){
                G[i].clear();
            }
            memset(vis,0,sizeof(vis));
            memset(mark,0,sizeof(mark));
            memset(in,0,sizeof(in));
            maxv = 0;
            flag = 1;
            times = 0;
           continue;
        }
        G[a].push_back(b);
        in[b]++;
        maxv = max(maxv,max(a,b));
        mark[a] = 1;
        mark[b] = 1;
        times++;
    }
    return 0;
}