# DFS

## 经典题目

### 1. 典型的，较为直观的DFS题。

[*200 Number of Islands*](https://legacy.gitbook.com/book/neil-haha/cc189/edit#)\
[*417 Pacific Atlantic Water Flow*](https://leetcode.com/problems/pacific-atlantic-water-flow/description/)

{% tabs %}
{% tab title="200" %}

```java
public int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0)  return 0;
    int n = grid.length;
    int m = grid[0].length;
    int res = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1') {
                res += 1;
                dfs(grid, i, j, n, m);
            }
        }
    }
    return res;
}

private void dfs(char[][] grid, int i, int j, int n, int m) {
    if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == '0') {
        return;
    }
    grid[i][j] = '0';
    dfs(grid, i + 1, j, n, m);
    dfs(grid, i, j + 1, n, m);
    dfs(grid, i - 1, j, n, m);
    dfs(grid, i, j - 1, n, m);
}
```

{% endtab %}

{% tab title="417" %}

```java
class Solution {
    private int[][] dirs = {{-1,0},{0,1},{1,0},{0,-1}};
    
    public List<int[]> pacificAtlantic(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return new ArrayList<int[]>();
        
        int n = matrix.length;
        int m = matrix[0].length;
        
        boolean[][] canTouchPacific = new boolean[n][m];
        boolean[][] canTouchAtlantic = new boolean[n][m];
        List<int[]> ans = new ArrayList<>();
        
        for (int i = 0; i < n; i++) {
            dfs(matrix, canTouchPacific, i, 0, Integer.MIN_VALUE);
            dfs(matrix, canTouchAtlantic, i, m - 1, Integer.MIN_VALUE);
        }
        
        for (int i = 0; i < m; i++) {
            dfs(matrix, canTouchPacific, 0, i, Integer.MIN_VALUE);
            dfs(matrix, canTouchAtlantic, n - 1, i, Integer.MIN_VALUE);
        }
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (canTouchPacific[i][j] && canTouchAtlantic[i][j]) {
                    ans.add(new int[]{i, j});
                }
            }
        }
        
        return ans;
    }
    
    private void dfs(int[][] matrix, boolean[][] sea, int row, int col, int prevHeight) {
        if (row < 0 || row >= sea.length || col < 0 || col >= sea[0].length || sea[row][col] || matrix[row][col] < prevHeight) {
            return;
        }
        sea[row][col] = true;        
        for (int i = 0; i < dirs.length; i++) {
            int newRow = row + dirs[i][0];
            int newCol = col + dirs[i][1];
            dfs(matrix, sea, newRow, newCol, matrix[row][col]);
        }
    }
}
```

{% endtab %}
{% endtabs %}

[*332. Reconstruct Itinerary*](https://leetcode.com/problems/reconstruct-itinerary/description/)

DFS。这题是基于一定有一个解的前提，所以我们不用考虑无解的情况。即最后一个点必然是没有出度的点。然后我们用DFS扫，找到的第一个没有出度的点即为最后一个点，第二个点即为最后第二个点，以此类推。。（因为在top down的过程中，对应的pq出栈，即为了防止进入死循环）

英文的描述：The idea is to keep following unused edges and removing them until we get stuck. Once we get stuck, we back-track to the nearest vertex in our current path that has unused edges, and we repeat the process until all the edges have been used.

```java
public List<String> findItinerary(String[][] tickets) {
    HashMap<String, PriorityQueue<String>> map = getMap(tickets);
    List<String> ans = new ArrayList<>();
    helper("JFK", map, ans);
    return ans;
}

private void helper(String cur, HashMap<String, PriorityQueue<String>> map, List<String> ans) {
    PriorityQueue<String> arrs = map.get(cur);
    while(arrs != null && !arrs.isEmpty()) {
        String arr = arrs.poll();
        helper(arr, map, ans);
    }
    ans.add(0, cur);
}

private HashMap<String, PriorityQueue<String>> getMap(String[][] tickets) {
    HashMap<String, PriorityQueue<String>> map = new HashMap<String, PriorityQueue<String>>();
    for (String[] t : tickets) {
        String dep = t[0];
        String arr = t[1];
        PriorityQueue<String> arrs = map.get(dep);
        if (arrs == null) {
            arrs = new PriorityQueue<String>();
        }
        arrs.add(arr);
        map.put(dep, arrs);
    }
    return map;
}
```

[*851 Loud and Rich*](https://leetcode.com/problems/loud-and-rich/description/)

```java
/*
    First build the graph.
    Then apply dfs to each node.
*/
public int[] loudAndRich(int[][] richer, int[] quiet) {
    List<List<Integer>> graph = buildGraph(richer, quiet.length);
    int[] ans = new int[quiet.length];
    Arrays.fill(ans, -1);
    for (int i = 0; i < quiet.length; i++) {
        cal(graph, i, quiet, ans);
    }
    return ans;
}

// DFS call to get minimum quietness among all people who have equal to or more
// money than person i.
private int cal(List<List<Integer>> graph, int i, int[] quiet, int[] ans) {
    if (ans[i] != -1) {
        return ans[i];
    }
    ans[i] = i;
    List<Integer> larger = graph.get(i);
    for (int large : larger) {
        int next = cal(graph, large, quiet, ans);
        if (quiet[ans[i]] >= quiet[next]) {
            ans[i] = next;
        }
    }
    return ans[i];
}

// Build Graph in the form of adjacent list
private List<List<Integer>> buildGraph(int[][] richer, int n) {
    // small : list of large
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<Integer>());
    }
    for (int i = 0; i < richer.length; i++) {
        int high = richer[i][0];
        int low = richer[i][1];
        graph.get(low).add(high);
    }
    return graph;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://mabuxi.gitbook.io/mabuxi/leetcode-summary/graph/dfs.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.