Problem: 【模板】拓扑排序
思路
拓扑排序模板
解题方法
- 初始化一个队列,将所有入度为0的顶点入队。
- 从队列中取出一个顶点,并将其输出。
- 对于该顶点的所有出边,将出边的终点的入度减1。
- 如果某个顶点的入度变为0,则将其入队。
- 重复步骤2-4,直到队列为空。
复杂度
时间复杂度:
时间复杂度: O ( V + E ) O(V+E) O(V+E),其中V是顶点数,E是边数。
空间复杂度:
空间复杂度: O ( V ) O(V) O(V),其中V是顶点数。
Code
import java.util.*;
import java.io.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static StreamTokenizer sr = new StreamTokenizer(in);
public static int MAXN = 200001;
public static int MAXM = 200001;
// 链式前向星建图
public static int[] head = new int[MAXN];
public static int[] next = new int[MAXM];
public static int[] to = new int[MAXN];
public static int cnt;
public static int[] queue = new int[MAXN];
public static int n, m, l, r;
public static int[] ans = new int[MAXN];
public static int[] indegree = new int[MAXN];
public static void build(int n) {
cnt = 1;
Arrays.fill(head, 0, n + 1, 0);
Arrays.fill(indegree, 0, n + 1, 0);
}
public static void addEdge(int f, int t) {
next[cnt] = head[f];
to[cnt] = t;
head[f] = cnt++;
}
public static void main(String[] args) throws IOException {
n = nextInt();
m = nextInt();
build(n);
for (int i = 0, from, to; i < m; i++) {
from = nextInt();
to = nextInt();
addEdge(from, to);
indegree[to]++;
}
if (!topoSort()) {
out.println(-1);
} else {
for (int i = 0; i < n - 1; i++) {
out.print(ans[i] + " ");
}
out.println(ans[n - 1]);
}
out.flush();
}
public static boolean topoSort() {
l = r = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0) {
queue[r++] = i;
}
}
int fill = 0;
while(l < r) {
int cur = queue[l++];
ans[fill++] = cur;
for(int ei = head[cur]; ei > 0; ei = next[ei]) {
if(--indegree[to[ei]] == 0) {
queue[r++] = to[ei];
}
}
}
return fill == n;
}
static int nextInt() throws IOException {
sr.nextToken();
return (int)sr.nval;
}
}