LeetCode 547. 省份数量

Categories:

题目描述
思路分析
1. 解法一：DFS 遍历连通分量（推荐）
相似题目

题目描述

✅ 547. 省份数量

思路分析

解法一：DFS 遍历连通分量（推荐）

核心思路：

城市之间的连通关系构成无向图，省份数量等于连通分量数量。

用 DFS 遍历邻接矩阵，访问一个未访问城市时计数加一。

访问过程中标记，避免重复遍历。

复杂度分析：

时间复杂度：O(n^2)，其中 n 为城市数量。

空间复杂度：O(n)，递归栈与访问数组占用。

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

        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                // 从未访问城市开始 DFS
                dfs(i, isConnected, visited);
                count++;
            }
        }

        return count;
    }

    private void dfs(int i, int[][] g, boolean[] visited) {
        visited[i] = true;
        for (int j = 0; j < g.length; j++) {
            if (g[i][j] == 1 && !visited[j]) {
                dfs(j, g, visited);
            }
        }
    }
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    count := 0

    var dfs func(i int)
    dfs = func(i int) {
        visited[i] = true
        for j := 0; j < n; j++ {
            if isConnected[i][j] == 1 && !visited[j] {
                dfs(j)
            }
        }
    }

    for i := 0; i < n; i++ {
        if !visited[i] {
            // 从未访问城市开始 DFS
            dfs(i)
            count++
        }
    }

    return count
}

相似题目

题目	难度	考察点
200. 岛屿数量	中等	DFS/BFS
695. 岛屿的最大面积	中等	DFS/BFS
684. 冗余连接	中等	并查集
721. 账户合并	中等	并查集
130. 被围绕的区域	中等	DFS/BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/55155236