【每日一题】Is It A Tree?

题目

给定由有向边连接的节点集合，判断是否是树。

多个案例，每个案例以 0 0 结束。整个输入以 -1 -1 结束。

解题思路

树有且只有一个根节点。
树中每个节点不能有多个父节点。
树中不能有环。
具体见代码。

注意：空树是树。

C++代码

#include<iostream>
#include<vector>
#include<set>
using namespace std;

bool dfs(int a, vector<int>& vis, vector<vector<int>>& edges){
    for(int i=0; i<edges[a].size(); ++i){
        int b = edges[a][i];
        if(vis[b]) return false;    // 有环，不是树
        vis[b] = true;
        bool flag = dfs(b, vis, edges);
        if(!flag) return false;
    }
    return true;
}

bool isTree(vector<vector<int>>& v, int n){
    if(v.empty()) return true;    // 是空树
    vector<vector<int>> edges(n+1);
    vector<int> fa(n+1,-1);
    set<int> st;
    for(int i=0; i<v.size(); ++i){
        int a = v[i][0];
        int b = v[i][1];
        if(a==b) return false;    // 自环，不是树
        edges[a].push_back(b);
        st.insert(a);
        st.insert(b);
        if(fa[b]==-1) fa[b]=a;
        else
            return false;    // 一个节点有多个父节点，不是树
    }
    int root = -1;
    for(set<int>::iterator it=st.begin(); it!=st.end(); ++it){
        int x = *it;
        if(fa[x]==-1){
            if(root==-1) root=x;
            else
                return false;    // 有多个根节点，不是树
        }
    }
    if(root==-1) return false;    // 没有根节点，有环，不是树
    vector<int> vis(n+1);
    vis[root] = true;
    return dfs(root, vis, edges);
}

int main(){
    int a, b;
    vector<vector<int>> v;
    int n = 0;
    int t = 1;
    while(cin >> a >> b){
        if(a==-1 && b==-1) break;
        if(a==0 && b==0){
            if(isTree(v,n))
                cout << "Case " << t << " is a tree." << endl;
            else
                cout << "Case " << t << " is not a tree." << endl;
            n = 0;
            ++t;
            v.clear();
        }
        else{
            vector<int> tmp;
            tmp.push_back(a);
            tmp.push_back(b);
            v.push_back(tmp);
            n = max(n, max(a,b));
        }
    }
    return 0;
}