LeetCode-DFS-图类-中等难度

547.省份数量

本题实际上就是求解图的连通分量个数。

public int findCircleNum(int[][] isConnected) {
    int ans = 0;
    int cities = isConnected.length;
    boolean[] visited = new boolean[cities];
    for (int i = 0; i < cities; i++) {
        if (!visited[i]) {
            visited[i] = true;
            dfs(isConnected, cities, i, visited);
            ans++;
        }
    }
    return ans;
}

private void dfs(int[][] isConnected, int cities, int idx, boolean[] visited) {
    for (int i = 0; i < cities; i++) {
        if (isConnected[idx][i] == 1 && !visited[i]) {
            visited[i] = true;
            dfs(isConnected, cities, i, visited);
        }
    }
}

1971.寻找图中是否存在路径

这是一道经典的求图中两个点是否连通的问题，直接使用邻接表法进行构图，然后从source开始遍历即可。

public boolean validPath(int n, int[][] edges, int source, int destination) {
    List<List<Integer>> edgeList = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        edgeList.add(new ArrayList<>());
    }
    for (int i = 0; i < edges.length; i++) {
        int s = edges[i][0];
        int d = edges[i][1];
        edgeList.get(s).add(d);
        edgeList.get(d).add(s);
    }
    boolean[] visited = new boolean[n];
    return dfs(edgeList, source, destination, visited);
}
private boolean dfs(List<List<Integer>> edgeList, int source, int destination, boolean[] visited) {
    if (source == destination) {
        return true;
    }
    visited[source] = true;
    for (int next : edgeList.get(source)) {
        if (!visited[next] && dfs(edgeList, next, destination, visited)) {
            return true;
        }
    }
    return false;
}

797.所有可能的路径

一道回溯算法的应用题

public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    dfs(ans, path, graph[0], 0, graph);
    return ans;
}
private void dfs(List<List<Integer>> ans, List<Integer> path, int[] arr, int idx, int[][] graph) {
    path.add(idx);
    if (idx == graph.length - 1) {
        ans.add(new ArrayList<>(path));
        return;
    }
    for (int i : arr) {
        dfs(ans, path, graph[i], i, graph);
        path.remove(path.size() - 1);
    }
}

841.钥匙和房间

本题实际上就是求解从顶点0开始，能否达到图中的所有点，所以本质上从0开始遍历，结束后检查下是否所有点都被访问过即可。

class Solution {
    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        int len = rooms.size();
        boolean[] visited = new boolean[len];
        dfs(visited, rooms, 0);
        for (int i = 0; i < visited.length; i++) {
            if (!visited[i]) {
                return false;
            }
        }
        return true;
    }

    private void dfs(boolean[] visited, List<List<Integer>> rooms, int idx) {
        visited[idx] = true;
        for (int next : rooms.get(idx)) {
            if (!visited[next]) {
                visited[idx] = true;
                dfs(visited, rooms, next);
            }
        }
    }  
}

2316.统计无向图中无法互相到达点对数

统计每个连通分量的大小，多个连通分量之间大小乘积之和即为结果。

public long countPairs(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        graph.add(new ArrayList<>());
    }
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    long ans = 0;
    int total = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            int size = dfs(visited, graph, i);
            ans += (long) total * size;
            total += size;
        }
    }
    return ans;
}

private int dfs(boolean[] visited, List<List<Integer>> graph, int idx) {
    visited[idx] = true;
    int size = 1;
    for (int next : graph.get(idx)) {
        if (!visited[next]) {
            size += dfs(visited, graph, next);
        }
    }
    return size;
}

2492.两个城市间路径的最小分数

从编号为1的城市开始，把所有的连通城市都遍历一次，找出最小的距离即可。

public int minScore(int n, int[][] roads) {
    List<int[]>[] graph = new ArrayList[n + 1];
    for (int i = 1; i <= n; i++) {
        graph[i] = new ArrayList<>();
    }
    for (int[] r : roads) {
        int a = r[0];
        int b = r[1];
        int d = r[2];
        graph[a].add(new int[]{b, d});
        graph[b].add(new int[]{a, d});
    }
    boolean[] visited = new boolean[n + 1];
    return dfs(graph, visited, 1);
}

private int dfs(List<int[]>[] graph, boolean[] visited, int idx) {
    visited[idx] = true;
    int min = Integer.MAX_VALUE;
    for (int[] next : graph[idx]) {
        min = Math.min(min, next[1]);
        if (!visited[next[0]]) {
            min = Math.min(min, dfs(graph, visited, next[0]));
        }

    }
    return min;
}

2685.统计完全连通分量的数量

在完全连通分量中，点集的大小与边集的大小关系应该是，边集大小 = 点集大小 * (点集大小 - 1) ÷ 2 因此，只需要求出每个连通分量中点集和边集的大小即可。

class Solution {
    
    int e = 0;
    int v = 0;
    
    public int countCompleteComponents(int n, int[][] edges) {
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            graph[e[0]].add(new int[]{e[1]});
            graph[e[1]].add(new int[]{e[0]});
        }
        boolean[] visited = new boolean[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            e = 0;
            v = 0;
            if (!visited[i]) {
                dfs(graph, visited, i);
                if (e == v * (v - 1)) {
                    ans++;
                }
            }
        }
        return ans;
    }

    // 如果是完全连通分量，则每个点都应该与所有点能直接连通。
    // 所以，通过graph[idx].size()，即可得到能与其直接连通的点的数量。
    // 注意：因为每个点都加了一次graph[idx].size()，相当于多加了一倍，
    // 所以在判断边集与点集的关系时直接用了e == v * (v - 1) 等价于 e/2 == (v * (v - 1))/2
    private void dfs(List<int[]>[] graph, boolean[] visited, int idx) {
        visited[idx] = true;
        v++;
        e += graph[idx].size();
        for (int[] next : graph[idx]) {
            if (!visited[next[0]]) {
                dfs(graph, visited, next[0]);
            }
        }
    }
}