解题思路

问题转化：将每个整数视为图中的节点，每对约束条件 (x, y) 视为从 x 到 y 的有向边。目标是找到一个满足拓扑顺序的序列，使得每个节点出现的次数等于给定的计数，并保证字典序最小。 拓扑排序：利用拓扑排序的思想，每次选择入度为 0 的节点，并优先处理数值较小的节点（使用优先队列保证）。 贪心策略：在每个步骤中，尽可能多地添加当前最小的合法数字，确保后续节点仍能满足约束。

算法原理

图模型： 节点：每个不同的整数 U（范围 0 到 m-1）。

边：约束对 (x, y) 表示必须存在从 x 到 y 的路径。

拓扑排序： 入度：每个节点的入度表示必须出现在它之前的不同节点数量。

优先队列：使用小顶堆（优先队列）确保每次取出的节点是当前入度为 0 的最小节点。

合法性检查： 若所有节点的入度最终都被消为 0，说明存在合法序列；否则输出 Impossible!。

实现步骤

1.输入处理： 读取整数数量 m 和约束对数 d。 读取每个整数的出现次数 counts。 读取约束对 (x, y)。

2.图构建： 初始化入度数组 in_degree 和邻接表 graph。 对每个约束对 (x, y)，增加 y 的入度，并将 y 添加到 x 的邻接表中。

3.拓扑排序初始化： 将所有入度为 0 且计数大于 0 的节点加入优先队列。

4.生成密钥： 从优先队列取出最小节点 u，将其所有出现次数加入结果序列。 减少 u 的所有邻居的入度，若邻居入度变为 0 且计数大于 0，则加入队列。

5.合法性验证： 检查所有节点的入度是否为 0，若存在非零入度的节点且计数大于 0，说明无解。

c++代码

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

vector<int> solve(int m, int d, vector<int>& counts, vector<pair<int, int> >& pairs) {
    map<int, int> in_degree;
    map<int, vector<int> > graph;

    // Initialize in_degree for all nodes
    for (int i = 0; i < m; ++i) {
        in_degree[i] = 0;
    }

    // Build the graph and in_degree
    for (vector<pair<int, int> >::iterator it = pairs.begin(); it != pairs.end(); ++it) {
        int x = it->first;
        int y = it->second;
        graph[x].push_back(y);
        in_degree[y]++;
    }

    // Use a priority queue to get the smallest lex order
    priority_queue<int, vector<int>, greater<int> > pq;

    // Add nodes with in_degree 0 to the priority queue
    for (int i = 0; i < m; ++i) {
        if (in_degree[i] == 0 && counts[i] > 0) {
            pq.push(i);
        }
    }

    vector<int> result;

    while (!pq.empty()) {
        int u = pq.top();
        pq.pop();

        // Add u to the result as many times as needed
        for (int i = 0; i < counts[u]; ++i) {
            result.push_back(u);
        }

        // Decrease in_degree for neighbors
        for (vector<int>::iterator it = graph[u].begin(); it != graph[u].end(); ++it) {
            int v = *it;
            in_degree[v]--;
            if (in_degree[v] == 0 && counts[v] > 0) {
                pq.push(v);
            }
        }
    }

    // Check if all nodes are processed
    for (int i = 0; i < m; ++i) {
        if (counts[i] > 0 && in_degree[i] != 0) {
            return vector<int>();
        }
    }

    return result;
}

int main() {
    int m, d;
    while (cin >> m >> d && (m != 0 || d != 0)) {
        vector<int> counts(m);
        for (int i = 0; i < m; ++i) {
            cin >> counts[i];
        }

        vector<pair<int, int> > pairs(d);
        for (int i = 0; i < d; ++i) {
            cin >> pairs[i].first >> pairs[i].second;
        }

        vector<int> result = solve(m, d, counts, pairs);

        if (result.empty()) {
            cout << "Impossible!" << endl;
        } else {
            for (size_t i = 0; i < result.size(); ++i) {
                if (i != 0) {
                    cout << " ";
                }
                cout << result[i];
            }
            cout << endl;
        }
    }
    return 0;
}