Day 63 || 拓扑排序、dijkstra

拓扑排序

题目链接：卡码网：117. 软件构建

思路：具体内容参考“代码随想录——拓扑排序精讲”。就是先找到入度为0的点，记录，然后找到该点出度指向的点，对该点的入度减一，如果为0入栈不为0的话继续，直至栈为空。查看结果数量和输入的点数量是否一致，不一致返回-1。

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int nums = sc.nextInt(); // 节点数int roads = sc.nextInt(); // 边数int[] in = new int[nums]; // 入度数组HashMap<Integer, List<Integer>> map = new HashMap<>(); // 邻接表表示出度关系// 读取边信息，构建图for (int i = 0; i < roads; i++) {int l = sc.nextInt();int r = sc.nextInt();// 增加入度in[r] += 1;// 初始化并添加出度列表map.putIfAbsent(l, new ArrayList<>());map.get(l).add(r);}// 存储拓扑排序结果StringBuilder res = new StringBuilder();// 拓扑排序：使用队列存储入度为0的节点Queue<Integer> queue = new LinkedList<>();for (int i = 0; i < nums; i++) {if (in[i] == 0) {queue.add(i);}}int count = 0; // 计数处理过的节点数while (!queue.isEmpty()) {int cur = queue.poll();res.append(cur).append(" ");count++;// 遍历当前节点的所有邻接节点，将其入度减1if (map.containsKey(cur)) {for (int neighbor : map.get(cur)) {in[neighbor]--;// 如果入度为0，加入队列if (in[neighbor] == 0) {queue.add(neighbor);}}}}// 检查是否所有节点都被处理了，如果有环，无法拓扑排序if (count != nums) {System.out.println(-1);} else {res.deleteCharAt(res.length() - 1); // 删除最后一个空格System.out.println(res.toString());}}
}

dijkstra

题目链接：卡码网：47. 参加科学大会

思路：具体内容参考“代码随想录——dijkstra（朴素版）精讲”。dijkstra三部曲：第一步，选源点到哪个节点近且该节点未被访问过；第二步，该最近节点被标记访问过；第三步，更新非访问节点到源点的距离（即更新minDist数组）。类似于prim算法，但是这个列表中存储的是到源点最近的距离，而非节点到最小生成树的最小距离。