首页 > 试题广场 >

有序图

[编程题]有序图

现在给出一张含有 n 个点的有向无环图，我们称这张图是“有序图”当且仅当这个图满足以下条件：

1. 存在一个 1-n 数字的全排列 p ，并令 i 号结点的权值为 p[i] 。

2. 如果图中存在 u 号结点到 v 号结点的一条边，则 u 号结点的权值要小于 v 号结点的权值。显然可能有多个序列满足条件，请你找出字典序最小的全排列 p ，使得这个图成为有序图。

数据范围： $1 \le n , m \le 10^5 \$

第一行包含两个正整数n，m,分别表示图上结点是数量和有向边的数量。 接下来m行每行有两个正整数u，v，表示存在一条从u结点到v结点的有向边。

输出一个字典序最小的，1-n的全排列，使得这张图是有序图，元素中间使用空格隔开。

示例1

输入

1 3 2

算法知识视频讲解

_Bingbong

发表于 2025-01-01 14:15:55

解题思路这是一个图论问题，通过反向建图和拓扑排序来找到字典序最小的全排列。关键点：反向建图：将所有边反向，便于从大到小分配数字使用最大堆维护可选节点从n到1逆序分配数字，保证字典序最小算法步骤：建立反向图的邻接表找出所有入度为的点加入最大堆每次取出堆顶元素，分配最大可用数展开全文

安卓工程师京东图 2019 排序

上传者：小小

难度：

7条回答 47收藏 7868浏览

查看代码

有序图

扫一扫，把题目装进口袋