拓扑排序
思想
利用图的BFS思想来处理
- 事件
A依赖于事件B，则添加一条A指向B的边 - 将所有入度为0的点加入到队列
- 从队列中弹出一个点，表示这个任务已经完成，遍历这个点指向了哪些点，将这些点的入度
-1，如果有点的入度减至为0则入队 - 最后结果数组中的点的个数要等于所有点的个数，否则这个图没有拓扑排序
关键数据结构
indegree[]：用来保存每个点的入度情况
AcWing 848. 有向图的拓扑序列 原题链接
注意，有自环的有向图没有拓扑排序
给定一个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≤1051≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
static int n;
static int m;
static List<List<Integer>> graph = new ArrayList<>();
static List<Integer> res = new ArrayList<>();
static int[] indegree;
private static void add(int a, int b) {
graph.get(a).add(b);
indegree[b]++;
}
public static void main(String[] args) {
n = in.nextInt();
m = in.nextInt();
indegree = new int[n + 1];
for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());
for (int i = 0; i < m; i++) add(in.nextInt(), in.nextInt());
if (topSort()) {
for (int x : res) out.print(x + " ");
out.println();
}else {
out.println("-1");
}
out.flush();
out.close();
}
private static boolean topSort() {
Queue<Integer> queue = new ArrayDeque<>();
for (int i = 1; i < n + 1; i++) if (indegree[i] == 0) queue.add(i);
while (!queue.isEmpty()) {
int idx = queue.poll();
res.add(idx);
List<Integer> list = graph.get(idx);
for (int x : list) {
indegree[x]--;
if (indegree[x] == 0) {
queue.add(x);
}
}
}
return res.size() == n;
}