题解 | #拓扑排序#
【模板】拓扑排序
https://www.nowcoder.com/practice/88f7e156ca7d43a1a535f619cd3f495c
import java.util.HashSet; import java.util.Scanner; import java.util.Set; class Vertex { public int inDegree = 0; public Set<Vertex> nexts = new HashSet<>(); public boolean isRemaining = true; } public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); final int N = in.nextInt(); final int M = in.nextInt(); Vertex[] vertexs = new Vertex[N]; for (int i = 0; i != N; ++i) { vertexs[i] = new Vertex(); } for (int i = 0; i != M; ++i) { int start = in.nextInt() - 1; int end = in.nextInt() - 1; vertexs[start].nexts.add(vertexs[end]); vertexs[end].inDegree++; } int numOfRemaining = N; int[] result = new int[N]; int k = 0; while (numOfRemaining > 0) { boolean found = false; for (int i = 0; i != N; ++i) { Vertex v = vertexs[i]; if (v.isRemaining && v.inDegree == 0) { found = true; v.isRemaining = false; for (Vertex next : v.nexts) { next.inDegree--; } numOfRemaining--; result[k++] = i + 1; } } if (!found) { break; } } if (numOfRemaining == 0) { StringBuilder sb = new StringBuilder(); for (int x : result) { sb.append(x + " "); } System.out.println(sb.toString().trim()); } else { System.out.println("-1"); } } }