【每日一题】Is It A Tree?

Is It A Tree?

https://ac.nowcoder.com/acm/problem/105905

题目

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

多个案例,每个案例以 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;
}
全部评论

相关推荐

有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司10个岗位
点赞 评论 收藏
分享
06-20 17:42
东华大学 Java
凉风落木楚山秋:要是在2015,你这简历还可以月入十万,可惜现在是2025,已经跟不上版本了
我的简历长这样
点赞 评论 收藏
分享
06-12 16:23
已编辑
小米_软件开发
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-21 13:38
8月实习会变多吗现在还没找到实习该怎么办...回复的hr好少
码农索隆:3-4月就要开始找,基本上6月份就发offer,7月初已经开始暑期实习了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务