字节跳动第三题

输入格式调了半天。。。

#include <bits/stdc++.h>

using namespace std;

int main() {
    string str;
    vector<vector<int>> vec;
    int num;
    while (getline(cin, str)) {
        stringstream ss(str);
        vector<int> vec1;
        while (ss >> num)
            vec1.push_back(num);
        vec.push_back(vec1);
    }
    int n = vec.size();
    vector<vector<int>> adj(n);
    vector<int> degree(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 1; j < vec[i].size(); j++) {
            adj[vec[i][j] - 1].push_back(i);
            ++degree[i];
        }
    queue<int> q;
    for (int i = 0; i < n; i++)
        if (degree[i] == 0)
            q.push(i);
    vector<int> res;
    while (!q.empty()) {
        int cur = q.front();
        res.push_back(cur);
        q.pop();
        n--;
        for (auto next:adj[cur])
            if (--degree[next] == 0)
                q.push(next);
    }
    if (n == 0) {
        for (int i = 0; i < res.size(); i++) {
            if (i != 0)
                cout << ' ';
            cout << res[i] + 1;
        }
    } else
        cout << -1;
    return 0;
}

应该找到错误了，上面的代码，输入测试用例

1
2 1
3 2
4 1
5 1 3 4
输出是1 2 4 3 5

把上面代码的queue换成priority_queue
结果就变成1 2 3 4 5了。。

附一下修改后的代码：

#include <bits/stdc++.h>

using namespace std;

int main() {
    string str;
    vector<vector<int>> vec;
    int num;
    while (getline(cin, str)) {
        stringstream ss(str);
        vector<int> vec1;
        while (ss >> num)
            vec1.push_back(num);
        vec.push_back(vec1);
    }
    int n = vec.size();
    vector<vector<int>> adj(n);
    vector<int> degree(n, 0);
    for (int i = 0; i < n; i++)
        for (int j = 1; j < vec[i].size(); j++) {
            adj[vec[i][j] - 1].push_back(i);
            ++degree[i];
        }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++)
        if (degree[i] == 0)
            pq.push(i);
    vector<int> res;
    while (!pq.empty()) {
        int cur = pq.top();
        res.push_back(cur);
        pq.pop();
        n--;
        for (auto next:adj[cur])
            if (--degree[next] == 0)
                pq.push(next);
    }
    if (n == 0) {
        for (int i = 0; i < res.size(); i++) {
            if (i != 0)
                cout << ' ';
            cout << res[i] + 1;
        }
    } else
        cout << -1;
    return 0;
}

#笔试题目##字节跳动#