学步园

题意：给你一堆边，有向边，然后这个图是否构成一颗树。

他这里树的定义是这样的：只有一个入度为0的点，是根节点。

每一个节点（除根节点）都只有一条边指向他，也就是入度等于1。

从根节点到任意一个节点的路径是唯一的。

满足上面三个要求的话就是树。

OK。那就可以搞了，A了之后看DISCUSS里面都说是并查集搞的，我是直接爆搜的。

思路：首先找出入度为0的点，如果有多个，那么不是树。

然后找度数大于1的，如果有，那么不是树。

最后从根节点爆搜一遍，看节点是否都只访问到一次。

注意0 0 的时候代表空树，他也是一颗树，我想这是这道题唯一的trick了。

#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <cstring>
#include <iostream>
#include <algorithm>
#define Max 2505
#define FI first
#define SE second
#define ll long long
#define PI acos(-1.0)
#define inf 0x3fffffff
#define LL(x) ( x << 1 )
#define bug puts("here")
#define PII pair<int,int>
#define RR(x) ( x << 1 | 1 )
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )

using namespace std;

#define N 111111
struct KK{
    int e , next ;
}ed[N] ;
int head[N] , num ;
void init(){
    mem(head , -1) ;num = 0 ;
}
void add(int s , int e ){
    ed[num].e = e ;ed[num].next = head[s] ; head[s] = num ++ ;
}
int in[N] , out[N] ;
int vis[N] ;
int iscr = 0 ;
void dfs(int now){
    vis[now] ++ ;
    iscr ++ ;if(iscr >= 1000000)return ;//怕SB数据死循环。
    for (int i = head[now] ; ~i ; i = ed[i].next ){
        int e = ed[i].e ;
        dfs(e) ;
    }
}
int main() {
    int a , b ;
    int mx = 0 , ca = 0 ;
    while(cin >> a >> b ){
        mx = 0 ;
        if(a == -1 && b == -1)break ;
        printf("Case %d ", ++ ca) ;
        if(!a && !b){
            puts("is a tree.") ;continue ;
        }
        init() ;
        mem(in , 0) ; mem(out ,0) ;mem(vis ,0) ;
        mx = max(max(a , b) , mx) ;

        out[a] ++ , in[b] ++ ;
        add(a , b) ;
        vis[a] = vis[b] = 1 ;

        while(cin >> a >> b , (a + b)){
            add(a , b) ;
            vis[a] = vis[b] = 1 ;
            mx = max(mx , max(a , b)) ;
            out[a] ++ , in[b] ++ ;
        }

        int root = -1 ;int rootnum = 0 ;bool isok = false ;
        for (int i = 1 ; i <= mx ; i ++ )if(vis[i] && in[i] == 0)root = i , rootnum ++ ;//根节点和根节点个数
        for (int i = 1 ; i <= mx ; i ++ )if(in[i] >= 2)isok = true ;//每个节点的度数
        if(root == -1 || rootnum >= 2 || isok)puts("is not a tree.") ;
        else{
            mem(vis ,0) ;
            dfs(root) ;
            iscr = false ;
            bool flag = false ;
            for (int i = 1 ; i <= mx ; i ++ )if(vis[i] >= 2)flag = true ;//访问到2次或者以上
            if(flag)puts("is not a tree.") ;
            else puts("is a tree.") ;
        }
    }
    return 0 ;
}