leetcode 547. Number of Provinces | 547. 省份数量（图的邻接矩阵 DFS）

小咪咪 2022-09-14 02:28 135阅读 0赞

## 题目 ##

[https://leetcode.com/problems/number-of-provinces/][https_leetcode.com_problems_number-of-provinces]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]

## 题解 ##

本题用了图的邻接矩阵 DFS。另外，也可以用并查集来做。

class Solution { 
        int n;
        int provinces = 0;
    
        public int findCircleNum(int[][] isConnected) { 
    
            n = isConnected.length;
            boolean[] visited = new boolean[n];
    
            for (int i = 0; i < n; i++) { 
                if (!visited[i]) { 
                    provinces++;
                    dfs(i, isConnected, visited);
                }
            }
            return provinces;
        }
    
    
        // from cur to unvisited next
        public void dfs(int cur, int[][] graph, boolean[] visited) { 
            if (cur >= n || visited[cur]) { 
                // pass
            } else { 
                visited[cur] = true;
                for (int next = 0; next < n; next++) { 
                    if (graph[cur][next] == 1) dfs(next, graph, visited);
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]

[https_leetcode.com_problems_number-of-provinces]: https://leetcode.com/problems/number-of-provinces/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a23ed10e1b47449b9d46caede2cb44d9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5a-S5rOJSHE_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/2d2f70a9383c4e1888b4453e6c6917d2.png