强迫症冒险家的任务清单：字典序最小拓扑排序-洪萨配资

题目名称：强迫症冒险家的任务清单

题目背景

在广阔的“代码大陆”上，有一位著名的冒险家。他虽然勇猛无双，但有一个让旁人无法理解的习惯——严重的强迫症。

冒险公会发布了N个委托任务，编号从1到N。这些任务之间往往存在逻辑关联，比如：“想去屠龙（任务B），必须先找到屠龙宝刀（任务A）”。也就是说，某些任务必须在另一个任务完成后才能开始。

这位冒险家做任务有两个原则：

绝对遵守规则：如果任务U是任务V的前置条件，他一定先完成U再去挑战V。
编号强迫症：当他手头有多个“当前立刻就能做”的任务时，他一定会优先选择编号最小的那一个去执行。

请你帮这位强迫症冒险家制定一份详细的任务执行顺序表。

题目描述

给定一个包含N个任务的清单，以及M条前置关系规则。

每条规则描述为u v，表示任务u必须在任务v之前完成。

请输出满足上述所有条件，且符合冒险家“编号优先”习惯的任务执行序列。

（题目保证给出的关系网是有向无环图，即一定存在可行解）。

输入格式

第一行包含两个整数N, M，分别表示任务的总数量和前置规则的数量。

接下来M行，每行包含两个整数u, v，表示任务u是任务v的前置任务。

输出格式

一行，包含N个整数，表示冒险家完成任务的顺序，整数之间用空格隔开。

输入输出样例

输入 #1

4 3 1 2 2 3 4 2

输出 #1

1 4 2 3

样例解释

任务关系：1->2, 4->2, 2->3。
一开始，任务1和任务4都没有前置条件，都可以做。
根据“编号强迫症”，冒险家选择更小的1。
做完1之后，当前能做的只有4（因为2还需要4完成才能解锁）。
冒险家做4。
此时1和4都做完了，任务2解锁。冒险家做2。
做完2，任务3解锁。冒险家做3。
最终顺序：1 4 2 3。

数据范围：

2<=n<=10000

0<=m<=100000

1<=u, v<=n, u!=v

1. 问题抽象与分析

核心模型

这个问题本质上是一个有向无环图（DAG）的拓扑排序问题：

节点：代表任务。
有向边u->v：代表u是v的前置条件。
拓扑序列：一个线性的执行顺序，满足所有依赖关系。

为什么普通的拓扑排序不行？

普通的Kahn算法（基于入度的拓扑排序）使用的是queue（普通队列）。

在普通队列中，如果同时有任务1和任务4解锁了（入度为 0），谁先入队谁就先出来。这无法保证“优先做编号最小的任务”。

举个例子：

假设任务1和4同时没有前置条件。

普通队列：可能输出4->1 ...
题目要求：必须输出1->4 ...

解决方案：优先队列

为了满足“强迫症”要求（字典序最小），我们需要把普通的先进先出队列换成小根堆。

容器选择：priority_queue。
排序规则：greater<int>（从小到大）。
逻辑：每次从堆里弹出的，一定是当前所有入度为0的节点中，编号最小的那个。

2. 输入输出格式

输入格式：

第一行输入两个整数n, m，表示任务数量和前置规则数量。

接下来m行，每行两个整数u, v，表示任务u必须在任务v之前完成。

输出格式：

一行n个整数，表示冒险家做任务的顺序。

样例输入：

4 3 1 2 2 3 4 2

(解释：1->2, 4->2, 2->3。一开始1和4都没前置，但1比4小，所以先做1，再做4，解锁2，最后3)

样例输出：

1 4 2 3

3. 完整代码

//字典序最小拓扑序 #include <iostream> #include <vector> #include <queue> using namespace std; int n,m; //默认大根堆需要修改为小根堆 priority_queue<int,vector<int>,greater<int>> q; vector<int> edge[10010]; int d[10010];//记录每个点的入度 int l[10010];//记录拓扑序列 void tuopu(){ //将所有入度为0的点入队 for(int i=1;i<=n;i++) if(d[i]==0) q.push(i); int tot=0;//记录l数组元素个数 while(!q.empty()){ int x=q.top();//访问队首元素 q.pop();//队首出队 l[++tot]=x; for(auto y:edge[x]){//遍历所有以x为起点的边的终点y 然后把边删了 d[y]--;//边删了 y入度减一 if(d[y]==0) q.push(y);//如果入度为0 就入队 } } for(int i=1;i<=tot;i++) cout<<l[i]<<" "; } int main(){ cin>>n>>m; //vector邻接表存图 for(int i=1;i<=m;i++){ int u,v; cin>>u>>v; edge[u].push_back(v); d[v]++; } tuopu();//拓扑排序 return 0; }

4. 复杂度分析

时间复杂度：O(N+MlogN)。
- 我们需要遍历图中的所有点和边，基础是O(N+M)。
- 但是，每次节点入队和出队的操作是基于堆的，复杂度为log(当前队列大小)。
- 最坏情况下（比如所有点一开始都入度为0），复杂度会上升到O(NlogN)。
空间复杂度：O(N+M)。
- 主要消耗在邻接表edge存储边，以及入度数组d。