题目描述
给定一个n个点m条边的有向图,点的编号是1到n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出-1。
若一个由图中所有点构成的序列A满足:对于图中的每条边(x, y),x在A中都出现在y之前,则称A是该图的一个拓扑序列。
输入格式
第一行包含两个整数n和m
接下来m行,每行包含两个整数x和y,表示存在一条从点x到点y的有向边(x, y)。
输出格式
共一行,如果存在拓扑序列,则输出拓扑序列。
否则输出-1。
数据范围
1≤n,m≤105
输入样例:
3 3
1 2
2 3
1 3
输出样例:
1 2 3
(时间复杂度) $O(m*n)$
C++ 代码
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int h[N], e[N], ne[N], i; // 定义邻接表
int top[N], d[N], k = 0; // 保存拓扑序,顶点入度表,拓扑序列的索引
void add(int a, int b) {
e[i] = b; // 保存值
ne[i] = h[a]; // 在链表头部插入节点
h[a] = i; // 更新邻接表的表头保存的链表的首节点的索引
i++; // 指针指向下一个空白节点
}
int topsort(int m) {
priority_queue<int> q;
for(int i = 0; i < m; i++) // 保存所有入度为0的顶点
if(d[i] == 0) q.push(i);
while(!q.empty()) {
auto t = q.top(); // 读取队列中的顶点作为遍历时的当前顶点
q.pop(); // 读完,清除垃圾数据
top[k++] = t; // 保存当前顶点到拓扑序列中,因为当前的顶点入度为0
for(int i = h[t]; ~i; i = ne[i]) { // 遍历从t位置处拉出的链表,这条链表保存了所有与t相邻的顶点
int j = e[i]; // 删除t->j的一条有向边
if(--d[j]) continue; // 顶点j的入度不为0,访问下一条有向边
q.push(j); // 否则,顶点j入队列
}
}
return k == m; // 完成操作后,索引的值必然等于顶点的总数
}
int main() {
memset(h, -1, sizeof h); // 初始化邻接表的表头
int m, n, a, b;
cin >> m >> n; // 输入顶点数以及有向边数
while(n--) { // 根据边数录入顶点以及确定有向边
cin >> a >> b;
add(a - 1, b - 1);
d[b - 1]++; // 对b来说增加了一条指向它的有向边,入度加一
}
if(topsort(m) == 0) cout << "-1"; // 不存在拓扑序
else for(int i = 0; i < m; i++) cout << top[i] + 1 << ' '; // 输出
return 0;
}