题目描述
给定一个 n 个点 m 条边的有向图,点的编号是 1 到 n,图中可能存在重边和自环。
请输出任意一个该有向图的拓扑序列,如果拓扑序列不存在,则输出 −1。
若一个由图中所有点构成的序列 A 满足:对于图中的每条边 (x,y),x 在 A 中都出现在 y 之前,则称 A 是该图的一个拓扑序列。
算法
思路:记录每个节点的入度数量,选取入度为0的点,将与入度为0点相邻的元素减去相应的入度数。以此反复
存储:邻接表,队列存储入度为0的点
具体代码
import java.util.*;
import java.io.*;
public class Main {
private static int N = 2 * 100010;
private static int idx = 0;
private static int[] e = new int[N];
private static int[] ne = new int[N];
private static int[] h = new int[N];
private static int[] d = new int[N]; // 记录每个节点的入度
private static int[] q = new int[N]; // 存储入度为零的节点
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] line = reader.readLine().split(" ");
int n = Integer.parseInt(line[0]);
int m = Integer.parseInt(line[1]);
Arrays.fill(h, -1);
for (int i=0; i<m; i++) {
line = reader.readLine().split(" ");
int n1 = Integer.parseInt(line[0]);
int n2 = Integer.parseInt(line[1]);
add(n1, n2);
d[n2]++;
}
if (topsort(n)) {
for (int i=0; i<n; i++)
System.out.print(q[i]+" ");
} else {
System.out.println(-1);
}
}
private static boolean topsort(int n) {
int hh = 0;
int tt = -1;
for (int i=1; i<=n; i++) {
if (d[i] == 0) 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;
}
private static void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
}