题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

#include<iostream>
#include<cstring>
#include<unordered_map>
#include<unordered_set>
#include<queue>
#include<vector>
#include<map>
#include<algorithm>

using namespace std;

const int N = 10010;
int n;
unordered_map<int, vector<int>> tree;
unordered_set<int> indegree;
unordered_set<int> st;
map<pair<int, int>, bool> edges;
unordered_map<int, int> timestamp;

vector<int> bfs(int root)
{
    queue<int >q;
    q.push(root);
    st.insert(root);
    vector<pair<int, int>> nodes;
    int d = 0;

    while(q.size())
    {
        int size = q.size();
        while(size --)
        {
            int t = q.front(); q.pop();
            nodes.push_back({d, t});
            for (auto x : tree[t])
            {
                if (st.count(x)) return vector<int>();
                q.push(x);
                st.insert(x);
            }
        }
        d ++;
    }
    vector<vector<int>> res;
    for (auto x : nodes) res.push_back({x.first, timestamp[x.second], x.second});//第几层， 输入顺序， 节点值；
    sort(res.begin(), res.end());//排序的过程；

    vector<int> ans;
    for(auto x : res) ans.push_back(x[2]);

    return ans;
}


int main()
{
    cin >> n;
    int tm = 0;
    for (int i = 0; i < n; i ++)
    {
        int a, b;
        scanf("%d,%d", &a, &b);
        if (edges[{a, b}]) continue;
        edges[{a, b}] = true;
        tree[a].push_back(b);
        indegree.insert(b);

        if (timestamp.count(a) == 0) timestamp[a] = tm ++;
        if (timestamp.count(b) == 0) timestamp[b] = tm ++;
    }

    int root = 0;
    for (auto x : timestamp)
    {
        if (!indegree.count(x.first))
        {
            root = x.first;
            break;
        }
    }

    if (root == 0) puts("Not a tree");
    else
    {
        auto res = bfs(root);
        if (res.size() < indegree.size()) puts("Not a tree");
        else 
        {
            for (int i = 0; i < res.size(); i ++) 
            {
                if (i == 0) cout << res[i];
                else cout << "," << res[i];
            }
        }
    }




}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla