题目描述 给定一个 个点 条边的有向图，求解一个特定的拓扑排序，该拓扑排序满足： 1号点出现位置尽可能早 在1号点出现尽可能早的前提下2号点出现位置尽可能早 在满足前面条件的前提下3号点出现位置尽可能早 以此类推 例如，4个点2条边，边为<3,1>，<4,1>，那么应当找到的拓扑排序为{3,4,1,2} 输入格式 第一行一个正整数 ，表示数据组数。 接下来是 组数据。 对于每组数据： 第一行两个用空格分开的正整数 和 ，分别表示点数和边数。 接下来 行，每行两个正整数 ，表示有一条从 到 的边。（注意，一条边有可能会被描述多次） 输出格式 输出文件仅包含 行，每行 个整数，表示符合题目要求的拓扑排序，或者”Impossible!”表示无解（不含引号）。 样例 样例输入 3 5 4 5 4 5 3 4 2 3 2 3 3 1 2 2 3 3 1 5 2 5 2 4 3 样例输出 1 5 3 4 2 Impossible! 1 5 2 4 3用C++

### 特殊规则的拓扑排序实现 为了满足题目需求，需设计一个特殊的拓扑排序算法，使得节点按照编号顺序尽可能靠前排列。以下是具体方法： #### 方法概述 1. 使用 **Kahn 算法** 实现拓扑排序[^2]。 2. 维护一个优先队列（最小堆），用于始终选取当前可访问节点中编号最小的一个[^5]。 3. 如果最终无法完全清空所有节点，则表示图中有环，返回 `-1` 表明无解。 #### C++ 实现代码 以下是一个完整的 C++ 实现方案，支持多组输入数据，并能够处理无解的情况。 ```cpp #include <iostream> #include <vector> #include <queue> using namespace std; // 主函数逻辑 int main() { int T; // 测试用例数量 cin >> T; while (T--) { int n, m; // 节点数和边的数量 cin >> n >> m; vector<vector<int>> adj(n + 1); // 邻接表 vector<int> indegree(n + 1, 0); // 入度数组 // 构建邻接表并计算入度 for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; adj[u].push_back(v); indegree[v]++; } priority_queue<int, vector<int>, greater<>> pq; // 小根堆，确保编号小的节点优先被处理 for (int i = 1; i <= n; ++i) { if (indegree[i] == 0) { pq.push(i); } } vector<int> topoOrder; // 存储拓扑序的结果 while (!pq.empty()) { int node = pq.top(); pq.pop(); topoOrder.push_back(node); for (auto &neighbor : adj[node]) { if (--indegree[neighbor] == 0) { pq.push(neighbor); } } } // 判断是否有环 if (topoOrder.size() != n) { cout << "-1\n"; // 图中有环，无解 } else { for (auto &node : topoOrder) { cout << node << " "; } cout << "\n"; } } return 0; } ``` #### 关键点解析 1. **优先队列的选择** 使用 `priority_queue<int, vector<int>, greater<>` 来构建一个小根堆，从而保证每次取出的节点都是当前可用节点中编号最小的那个。 2. **入度初始化与更新** 对于每一个节点，记录其入度值。只有当某个节点的入度降为零时，才将其加入优先队列[^4]。 3. **判断是否存在环** 若最终得到的拓扑序列长度不等于总节点数 $n$，则说明图中存在环，应输出 `-1` 表示无解[^3]。 4. **多组测试数据的支持** 外层循环控制多个测试用例的读取与处理，确保程序可以一次性处理多组输入数据。 --- ###