**841. 钥匙和房间（DFS入门）**

Set<Integer> set = new HashSet<>();
public boolean canVisitAllRooms(List<List<Integer>> rooms) {
    set.add(0);
    dfs(rooms, 0);
    return set.size() == rooms.size();
}
public void dfs(List<List<Integer>> rooms, int k) {
    List<Integer> list = rooms.get(k);
    for(int i = 0; i < list.size(); i++) {
        int room = list.get(i);
        if(!set.contains(room)) {
            set.add(room);
            dfs(rooms, room);
        }
    }
}

**547. 省份数量（DFS练习）**

class Solution {
boolean[] visited;
int ans;
int n;
public int findCircleNum(int[][] isConnected) {
    n = isConnected.length;
    visited = new boolean[n];

    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            dfs(isConnected, i);
            ans++;
        }
    }
    return ans;
}
public void dfs(int[][] isConnected, int k) {
    for(int i = 0; i < isConnected[k].length; i++) {
        if(isConnected[k][i] == 1 && visited[i] == false) {
            visited[i] = true;
            dfs(isConnected, i); 
        }
    }
}
}

**1466. 重新规划路线（DFS 有向图转无向图）**

思路：先按无向图搜索依次，如果方向不一样，变更次数++

class Solution {
    Set<Integer> set = new HashSet<>();
    int ans = 0;
    ArrayList<HashMap<Integer,Integer>> graph;
    int[][] d_graph;
    int n;
    public int minReorder(int _n, int[][] connections) {
        n = _n;
        ArrayList<HashMap<Integer,Integer>> graph = new ArrayList<>(n);
        for(int i = 0; i < n; i++) {
            HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
            graph.add(map);
        }
        for(int[] edge : connections) {
            graph.get(edge[0]).put(edge[1], 1); // 原始边
            graph.get(edge[1]).put(edge[0], 2); // 虚拟边
        }
        // 遍历搜索
        set.add(0);
        dfs(0);
        return ans;
    }
    public void dfs(int cur) {
        for (Map.Entry<Integer, Integer> entry : graph.get(cur).entrySet()) {
            int key = entry.getKey(), value = entry.getValue();
            if(!set.contains(key)) {
								// 方向不一样，变更次数+1
                if(value == 1) ans++;
                set.add(key);
                dfs(key);
            }
        }
    }
}

**1926. 迷宫中离入口最近的出口（BFS入门）**

public int nearestExit(char[][] maze, int[] entrance) {
    int n = maze.length;
    int m = maze[0].length;

    Queue<int[]> q = new LinkedList<>();
    int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}};
    maze[entrance[0]][entrance[1]] = '+';
    q.add(new int[]{entrance[0], entrance[1], 0});
    // BFS遍历
    while(!q.isEmpty()) {
        int[] front = q.poll();
        for(int i = 0; i < 4; i++) {
            int x = front[0] + direct[i][0];
            int y = front[1] + direct[i][1];
            int step = front[2];
            if(x < 0 || x >= n || y < 0 || y >= m) continue;
            if(maze[x][y] == '+') continue;
            if(x == 0 || x == n-1 || y == 0 || y == m-1) return step + 1;
            maze[x][y] = '+';
            q.add(new int[]{x, y, step + 1});
        }
    }
    return -1;
}

**994. 腐烂的橘子（多源BFS）**

public int orangesRotting(int[][] grid) {
    int n = grid.length;
    int m = grid[0].length;

    // 收集多个起点
    Queue<int[]> q = new LinkedList<>();
    int[][] direct = {{0,1},{0,-1},{1,0},{-1,0}};
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 2) {
                q.add(new int[]{i, j});
                grid[i][j] = 2;
            }
        }
    }
    // BFS进行遍历
    int count = 0;
    while(!q.isEmpty()) {
        int size = q.size();
        for(int j = 0; j < size; j++) {
            int[] front = q.poll();
            for(int i = 0; i < 4; i++) {
                int x = front[0] + direct[i][0];
                int y = front[1] + direct[i][1];
                if(x < 0 || x >= n || y < 0 || y >= m) continue;
                if(grid[x][y] == 2 || grid[x][y] == 0) continue;
                grid[x][y] = 2;
                q.add(new int[]{x, y});
            }
        }
        if(q.size() == 0) break;
        count++;
    }
    // 判断还有没有正常的橘子
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(grid[i][j] == 1) {
                return -1;
            }
        }
    }
    return count;
}