感受

思路






#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 10;
struct edge{
    int v, nex;
}e[maxn];
int head[maxn], cnt, in[maxn], n;
int vis[maxn], has, dfn;
void add_edge(int u, int v){
    e[cnt].v = v;
    e[cnt].nex = head[u];
    head[u] = cnt++;
}
void init(){
    dfn = cnt = 0;
    for(int i = 1; i <= n; i++){
        head[i] = -1; vis[i] = 0; in[i] = -1;
    }
}
void dfs(int u, int tim){
    if(has) return ;
    vis[u] = tim;
    int v;
    for(int i = head[u]; ~i; i = e[i].nex){
        v = e[i].v;
        if(vis[v] == tim){
            has = true;
            break;
        }
        dfs(v, tim);
    }
}
bool check(){
    int num[2]; num[0] = num[1] = 0;
    for(int i = 1; i <= n; i++){
        if(in[i] > 1) return false;
        num[in[i]]++;
    }
    if(num[0] > 1) return false;
    if(num[0] == 0 && num[1] > 0) return false;
    return true;
}
int main(){
    int kase = 0;
    while(1){
        kase++;
        int u, v; bool ok = true; n = 0;
        vector<pair<int, int>> vec;
        while(scanf("%d%d", &u, &v), u + v){
            if(u == -1 && v == -1){
                ok = false; break;
            }
            vec.push_back(make_pair(u, v));
            n = max(n, u); n = max(n, v);
        }
        if(!ok) break;
        init(); has = false;
        for(int i = 0; i < vec.size(); i++){
            u = vec[i].first; v = vec[i].second;
            add_edge(u, v);
            if(in[v] < 0) in[v] = 0;
            if(in[u] < 0) in[u] = 0;
            in[v]++;
        }
        for(int i = 1; i <= n && !has; i++){
            if(!vis[i]){
                ++dfn;
                dfs(i, dfn);
            }
        }
        if(has || !check()){
            printf("Case %d is not a tree.\n", kase);
        }
        else{
            printf("Case %d is a tree.\n", kase);
        }
    }
    return 0;
}