再开下一个坑，图论专题居然以前都刷过了，三道Medium也没什么好说的，直接过

994. Rotting Oranges[Medium]

发现一个很神奇的事，这一题我再5年前的时候做，还是个Easy，现在已经涨到Medium了。看来随着通货膨胀，连Leetcode的题难度也跟着一起膨胀了

看了一下，原先的思路是拆分成三个函数，check用来检测好橘子的数量，legal用于判断是否搜索到边界，grow用于进行新的一天的搜索。

算一下时间复杂度，假设区域大小为 $m \times n$ ，最终需要 $d$ 天搜索完。单次grow需要往四个方向扩展，加一次原图恢复，总计 $O(5mn)$ 的复杂度，单次check复杂度为 $O(mn)$ ，每天的判断包含一次grow和两次check，总计 $O(7mn)$ ，再加一次初始化的check。整个流程的总复杂度为 $O((7d+1)\times mn)$

LeetCodeGOGOGO刷题记06——夯实基础（预处理）_Rotting Oranges-CSDN博客

接下来开始我的表演，直接bfs

先算一下时间复杂度，假设包含 $f$ 个新鲜的橘子和 $r$ 个坏掉的橘子， $f+r \leq m \times n$ 。一次初始化的 $O(mn)$ ，加上搜索节点 $O(4\times (f+r))$ ，总计 $O(mn + 4\times (f+r))\leq O(5mn)$ 。明显快多了

200. Number of Islands[Medium]

思路：典型的dfs，和之前的回溯专题极其类似，那就不多说了，直接上代码

/*
Author Owen_Q
*/
public class IslandsNumbers {public static int numIslands(char[][] grid) {int n = grid.length;int m = grid[0].length;int count = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '1') {count++;dfs(grid, i, j);}}}return count;}private static void dfs(char[][] grid, int i, int j) {int n = grid.length;int m = grid[0].length;if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0') {return;}grid[i][j] = '0';dfs(grid, i - 1, j);dfs(grid, i + 1, j);dfs(grid, i, j - 1);dfs(grid, i, j + 1);}}

207. Course Schedule[Medium]

思路：这就是个典型的拓扑排序判环问题。那么经典的BFS和DFS，刚好都来试一下

BFS

BFS就是经典队列问题，用一个队列来维护入度为0的节点。遍历队列中的点，将每个点的后继节点入度减一，并将入度减为0的节点放入队列中。若拓扑中存在环，则环上点永远不会进入队列，也不会度数降到1，因此只要判断是否存在入度不为0的点即可。

/*
Author Owen_Q
*/
public class CourseScheduler {public static boolean canFinishBfs(int numCourses, int[][] prerequisites) {List<List<Integer>> nextCourses = new java.util.ArrayList<>();for (int i = 0; i < numCourses; i++) {nextCourses.add(new java.util.ArrayList<>());}int[] inDegrees = new int[numCourses];Queue<Integer> processingCourses = new java.util.LinkedList<>();for (int[] prerequisite : prerequisites) {int course = prerequisite[0];int preCourse = prerequisite[1];nextCourses.get(preCourse).add(course);inDegrees[course]++;}for (int i = 0; i < numCourses; i++) {if (inDegrees[i] == 0) {processingCourses.offer(i);}}while (!processingCourses.isEmpty()) {Integer course = processingCourses.poll();numCourses--;for (Integer nextCourse : nextCourses.get(course)) {inDegrees[nextCourse]--;if (inDegrees[nextCourse] == 0) {processingCourses.offer(nextCourse);}}}return numCourses == 0;}
}

DFS

DFS其实就是经典的递归问题，需要用一个数组来记录每个点的访问情况。这里可以维护一个点的状态机。包含未访问，访问中和访问完成三种状态，访问中和访问完成分别对应dfs的入口和出口处。由于递归是个回溯问题，因此需要从后往前递推，当回溯到访问中的节点时即表示出现环，否则则表示顺利访问。于是遍历每个节点看能否顺利访问完所有节点即可

/*
Author Owen_Q
*/
public class CourseScheduler {public static boolean canFinishDfs(int numCourses, int[][] prerequisites) {int[] visited = new int[numCourses];List<List<Integer>> preCourses = new java.util.ArrayList<>();for (int i = 0; i < numCourses; i++) {preCourses.add(new java.util.ArrayList<>());}for (int[] prerequisite : prerequisites) {int course = prerequisite[0];int preCourse = prerequisite[1];preCourses.get(course).add(preCourse);}for (int i = 0; i < numCourses; i++) {if (visited[i] == 0) {if (canNotFinishDfs(i, visited, preCourses)) {return false;}}}return true;}private static boolean canNotFinishDfs(int course, int[] visited, List<List<Integer>> preCourses) {if (visited[course] == 0) {visited[course] = 1;for (Integer preCourse : preCourses.get(course)) {if (canNotFinishDfs(preCourse, visited, preCourses)) {return true;}}} else if (visited[course] == 1) {return true;}visited[course] = 2;return false;}
}

完结撒花