0.9 图论

[200.岛屿数量](https://leetcode.cn/problems/number-of-islands/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def dfs(self, grid, i, j):
        if not (0 <= i < len(grid) and 0 <= j < len(grid[0]) and grid[i][j] == '1'):
            return
        grid[i][j] = '2'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j-1)
        self.dfs(grid, i, j+1)
        
    def numIslands(self, grid: List[List[str]]) -> int:
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    res += 1
                    self.dfs(grid, i, j)
        return res
```
[994.腐烂的橘子](https://leetcode.cn/problems/rotting-oranges/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid),len(grid[0])
        q = deque()
        fresh = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    fresh += 1
                if grid[i][j] == 2:
                    q.append((i,j))
        ans = 0
        while q and fresh:
            size = len(q)
            ans += 1
            for _ in range(size):
                x, y = q.popleft()
                for i, j in (x+1, y),(x-1, y),(x,y+1),(x,y-1):
                    if 0<= i < m and 0 <= j < n and grid[i][j] == 1:
                        q.append((i,j))
                        grid[i][j] = 2
                        fresh -= 1
        return -1 if fresh else ans
```
[207. 课程表](https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegree = [0] * numCourses
        graph = [[] for _ in range(numCourses)]
        for cur, pre in prerequisites:
            indegree[cur] += 1
            graph[pre].append(cur)
        q = deque()
        for i in range(numCourses):
            if indegree[i] == 0:
                q.append(i)
        while q:
            pre = q.popleft()
            numCourses -= 1
            for cur in graph[pre]:
                indegree[cur] -= 1
                if indegree[cur] == 0:
                    q.append(cur)
        return numCourses == 0
```