题目描述
给定一个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
思路
1.添加所有边,记录每个节点的入度值
2.遍历所有节点,将入度值为0的节点放入到队列中
3.队列不为空的情况下
3.1 t <— 队头入度为0的节点出队
3.2 枚举t节点的所有出边,t -> j;
3.2.1删除所有出边,即调整d[j],d[j] –
3.2.2如果d[j] == 0 ,入队
如果所有元素都加进来,则 tt == n - 1, 否则返回-1,表示不存在拓扑结构
其中拓扑元素的顺序在队列中。
java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main{
static int n, m;
static int N = 100010;
static int[] e = new int[N], ne = new int[N], h = new int[N];
static int idx;
static int[] d = new int[N];
static Queue<Integer> queue = new LinkedList<>();
static ArrayList<Integer> q = new ArrayList<>(); // 记录点
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++;
}
private static boolean topSort(){
for (int i = 1; i <= n; i++) {
if (d[i] == 0) {
queue.offer(i);
q.add(i);
}
}
while (!queue.isEmpty()) {
int t = queue.poll();
for (int i = h[t]; i != -1 ; i = ne[i]) {
int j = e[i];
d[j] --;
if (d[j] == 0) {
queue.offer(j);
q.add(j);
}
}
}
return q.size() == n;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < N; i++) {
h[i] = -1;
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt();
int b = sc.nextInt();
add(a, b);
d[b] += 1;
}
if (topSort()) {
for (int i = 0; i < q.size(); i++) {
System.out.print(q.get(i) + " ");
}
} else {
System.out.println(-1);
}
}
}
python
N = 100010
h, e, ne = [-1] * N, [0] * N, [0] * N
d = [0] * N
n, m, idx = 0, 0, 0
queue = list()
q = list()
def add(a, b):
global idx
e[idx] = b
ne[idx] = h[a]
h[a] = idx
idx += 1
def topSort():
for i in range(1, n + 1):
if d[i] == 0:
queue.append(i)
q.append(i)
while queue:
t = queue.pop(0)
i = h[t]
while i != -1:
j = e[i]
d[j] -= 1
if d[j] == 0:
queue.append(j)
q.append(j)
i = ne[i]
return len(q) == n
def main():
global n, m
n, m = map(int, input().split())
for i in range(m):
a, b = map(int, input().split())
add(a, b)
d[b] += 1
if topSort():
for i in range(n):
print(q[i], end=" ")
else:
print(-1)
if __name__ == '__main__':
main()
c++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N]; //d表示点的入度
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort(){
int hh = 0, tt = -1;
for(int i = 1; i <= n; i ++){ //节点从1开始
if(!d[i]) q[++ tt] = i;
}
while(hh <= tt){
int t = q[hh ++];
for(int i = h[t]; i != -1; i = ne[i]){
int j = e[i];
d[j] --;
if(d[j] == 0) q[++ tt] = j;
}
}
return tt == n - 1;
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i < m; i ++){
int a, b;
cin >> a >> b;
add(a, b);
d[b] ++;
}
if(topsort()){
for(int i = 0; i < n; i ++) cout << q[i] << " ";
}else{
puts("-1");
}
}