华为软件类笔试-嵌入式软件开发 9-6

《嵌入式软件开发笔试与面试手册》：https://blog.nowcoder.net/zhuanlan/jvN8gj

《软件开发笔试汇总》：https://blog.nowcoder.net/zhuanlan/0oDWVm

3、设备配置数据排序

在现代网络通信设备中,设备的配置数据是一个队列集合。

当前设备配置数据存在全局唯一序号id标志此身份,还有一个字段决定此条配置数据的位置信息position。

通常,position支持如下几种格式:

1、first:队列头,编码格式: $id $id -1

2、end:处于队列尾部,编码格式:$id -1 $id

3、before $id1:表示$id应该在$id1数据之题,编码格式:$id $id $id1.

4、after $id1:表示$id应该在$id1数据之后，编码格式:$id $id1 $id

5、无特别排序指令的id数据,编码格式:$id -1 -1

当存在多种排序结果均满足上述排序要求的,则按照id第一次出现在排序指令队列的前后关系排序,以保证唯一顺序;

假定你已收到设备配置数据排序指令队列,需要正确计算出符合排序指令要求的数据id序列。

解答要求

时间限制:C/C++1000ms,其他语言:2000ms

内存限制:C/C++256MB,其他语言:512MB

输入

第一行代表本次的总配置数据数量，不超过100000;

其余行对应每个具体配置数据id和排序要求。id超过100000;

输出

输出按照要求排序好的数据id序列。

若当前排序指令存在问题,无法排序,则输出-1

样例1

输入:

5

1 -1 -1

2 -1 2

3 1 3

4 4 -1

5 4 5

输出:

4 1 3 5 2

样例2

输入:

3

1 -1 -1

2 2 -1

3 -1 -1

输出:

2 1 3

解释:

1和3的position为空,且无其他指令约束,则按照输入顺序排序;

样例3

输入:

3

1 1 -1

2 -1 2

3 2 3

输出:

-1

解释:

2已经是end,3不能再after end，无法排序，输出-1

样例4

输入:

4

1 1 3

2 2 4

3 -1 -1

4 -1 -1

输出:

1 2 3 4

解释:对于存在非严格限制顺序的场景,则按照数据输入的前后顺序排序,例如1在前,2在后,3在2后。

样例5

输入:

4

1 1 3

2 2 3

3 1 3

3 -1 -1

输出:

1 2 3

解释:

1在2后出现,3出现自然序最后,且同时满足2种排序指令。

样例6

输入:

4

2 1 2

1 1 3

3 -1 -1

2 -1 -1

输出:

1 2 3

解释:

1在2前,1在3前，且3在1,2之后自然顺序出现,2出现2次约束,一次是2 1 2前后排序约束,第二次是2 -1 -1无特殊顺序约束,则优先按照有排序指令的规则,同时在出现多个备选答案下，再考虑各数字出现的首次位置;

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

using namespace std;

int main() {
    int N;
    cin >> N;

    unordered_map<int, vector<int>> graph;
    unordered_map<int, int> indegree;
    unordered_set<int> nodes;
    unordered_map<int, int> lvl;
    int head = -1, tail = -1;

    for (int i = 0; i < N; ++i) {
        int a, b, c;
        cin >> a >> b >> c;

        if (lvl.find(a) == lvl.end()) {
            lvl[a] = i;
        }

        if (a == b && c == -1) {
            head = a;
        } else if (a == c && b == -1) {
            tail = a;
        } else if (a == b && c != -1) {
            indegree[c]++;
            graph[a].push_back(c);
        } else if (a == c && b != -1) {
            indegree[a]++;
            graph[b].push_back(a);
        }

        if (a != -1) nodes.insert(a);
        if (b != -1) nodes.insert(b);
        if (c != -1) nodes.insert(c);
    }

    queue<int> q;
    for (int k : nodes) {
        if (indegree[k] == 0) {
            q.push(k);
        }
    }

    vector<int> res;
    int cnt = 0;
    while (!q.empty()) {
        int size = q.size();
        cnt += size;
        vector<int> tmp;
        for (int i = 0; i < size; ++i) {
            int node = q.front();
            q.pop();
            if (node != head && node != tail) {
                tmp.push_back(node);
            }
            for (int next : graph[node]) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.push(next);
                }