题解 | #【模板】拓扑排序#
【模板】拓扑排序
https://www.nowcoder.com/practice/88f7e156ca7d43a1a535f619cd3f495c
import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; /** * @BelongsProject: homework * @Author: Ling xi_Li * @CreateTime: 2023-11-07 10-20 * @Description: TODO 拓扑排序 卡恩算法 */ public class Main { public static void main(String[] args) throws IOException { //AC的关键,得加速输入输出,因为这个卡了好久。。。。。。 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); String[] firstLine = in.readLine().split(" "); //输入点数 int vNums = Integer.parseInt(firstLine[0]); //输入边数 int eNums = Integer.parseInt(firstLine[1]); //用顺序表里面嵌套顺序表来代替图结构 //嵌套的列表就相当于点,里面存储了它可达的下一个点 ArrayList<ArrayList<Integer>> Graph = new ArrayList<>(vNums); //初始化点 for (int i = 0; i < vNums; i++) { Graph.add(new ArrayList<>()); } //输入边and//点的入度初始化 int vb = 0; int ve = 0; int[] Infiltration = new int[vNums];//数组大小和点数量一致,一个点对应一个入度 for (int i = 0; i < eNums; i++) { String[] edges = in.readLine().split(" "); //起始点 vb = Integer.parseInt(edges[0]); //被指向点 ve = Integer.parseInt(edges[1]); //因为列表索引0开始,点的数值1开始,通过vb-1来获取对应的点 Graph.get(vb - 1).add(ve - 1); //对应的第i个ve点的入度+1 Infiltration[ve - 1]++; } in.close(); //初始化队列 Queue<Integer> queue = new LinkedList<>(); for (int i = 0; i < vNums; i++) { //如果点的入度为0则入队 if (Infiltration[i] == 0) { queue.add(i); } } //存储结果的列表 ArrayList<Integer> result = new ArrayList<>(); //统计点的个数看看存不存在环 int countV = 0; //卡恩算法 while (!queue.isEmpty()) { //出队元素加入结果列表同时点个数加一 int cur = queue.poll(); result.add(cur); countV++; //依次遍历出队点(入度为0的点)点对应的下一个点然后将其下一个点的入度-1 for (int index : Graph.get(cur)) { if (--Infiltration[index] == 0) { queue.add(index); } } } if (countV == vNums) { //出队 for (int i = 0; i < result.size() - 1; i++) { //输出res+1是因为在 // 初始化图列表时候应下标需要对应的点值都-1了 // 然后包括添加到queue等一系列操作 // 都是在操作对应下标现在需要打印了所以+1还原 out.write(result.get(i) + 1 + " "); } //1 2 3 4 5 // 复制样例过来看输出最后一个后面没有空格 out.write((result.get(result.size() - 1) + 1) + "\n"); } else { //最后一个输出没有空格 String str = "-1"; out.write(str); } out.close(); } }