547. 省份数量
题目描述
共有 n 座城市，编号 0 到 n - 1。输入一个 n x n 矩阵 isConnected：isConnected[i][j] = 1 表示城市 i 和城市 j 之间有直达道路，等于 0 表示没有。
连通关系可以传递：若 a 能到 b，b 能到 c，那么 a 与 c 也算相连。彼此能够相互到达、并且不包含任何其他城市的一组城市称为一个省份。
返回省份的总数。
示例 1
输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]] 输出：2
解释：城市 0 和 1 相连，城市 2 独立，共 2 个省份。
示例 2
输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]] 输出：3
解释：三座城市互不相连，各成一个省份。
数据范围
1 <= n <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]为 1 或 0。isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
解题思路：深度优先搜索
省份就是无向图的连通分量。按编号扫描城市，遇到还没访问的城市 i，说明它属于一个新省份：计数加 1，并从 i 出发 DFS，把同一省份的城市全部标记为已访问。之后扫到这些城市会直接跳过，所以每个省份只被计数一次。
为什么正确
外层循环处理到 i 时，所有已访问的城市恰好属于已经计数过的省份。
复杂度分析
时间 O(n^2)，每个城市访问一次并扫描一整行；空间 O(n)。
易错点
计数要放在“发现未访问城市”的时候，而不是每访问一个城市就加 1；DFS 内也必须检查 visited，否则会在环上无限递归。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
visited = [False] * n
def dfs(i):
visited[i] = True
for j in range(n):
if isConnected[i][j] == 1 and not visited[j]:
dfs(j)
provinces = 0
for i in range(n):
if not visited[i]:
dfs(i)
provinces += 1
return provincesclass Solution {
int n;
boolean[] visited;
int[][] isConnected;
public int findCircleNum(int[][] isConnected) {
this.isConnected = isConnected;
n = isConnected.length;
visited = new boolean[n];
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
provinces++;
}
}
return provinces;
}
void dfs(int i) {
visited[i] = true;
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
dfs(j);
}
}
}
}class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> visited(n, false);
function<void(int)> dfs = [&](int i) {
visited[i] = true;
for (int j = 0; j < n; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
dfs(j);
}
}
};
int provinces = 0;
for (int i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
provinces++;
}
}
return provinces;
}
};func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
visited := make([]bool, n)
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)
}
}
}
provinces := 0
for i := 0; i < n; i++ {
if !visited[i] {
dfs(i)
provinces++
}
}
return provinces
}var findCircleNum = function(isConnected) {
const n = isConnected.length;
const visited = new Array(n).fill(false);
const dfs = (i) => {
visited[i] = true;
for (let j = 0; j < n; j++) {
if (isConnected[i][j] === 1 && !visited[j]) {
dfs(j);
}
}
};
let provinces = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
provinces++;
}
}
return provinces;
};function findCircleNum(isConnected: number[][]): number {
const n = isConnected.length;
const visited = new Array(n).fill(false);
const dfs = (i: number): void => {
visited[i] = true;
for (let j = 0; j < n; j++) {
if (isConnected[i][j] === 1 && !visited[j]) {
dfs(j);
}
}
};
let provinces = 0;
for (let i = 0; i < n; i++) {
if (!visited[i]) {
dfs(i);
provinces++;
}
}
return provinces;
}其他解法
三种解法都要扫描整个邻接矩阵；深度优先搜索和广度优先搜索按连通块逐个标记，并查集逐条合并边，适合动态连通性问题。
解法 2：广度优先搜索 时间 O(n²)，空间 O(n)
依次检查每个城市。遇到未访问的城市就把省份数加一，并把它放入队列。不断取出队首城市，扫描邻接矩阵的一行，把相连且未访问的城市标记后入队。队列变空时，这个省份的所有城市都已标记。
和深度优先搜索复杂度相同。用队列代替递归，不受递归深度限制。
from collections import deque
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
visited = [False] * n
provinces = 0
for i in range(n):
if visited[i]:
continue
provinces += 1
visited[i] = True
q = deque([i])
while q:
u = q.popleft()
for v in range(n):
if isConnected[u][v] == 1 and not visited[v]:
visited[v] = True
q.append(v)
return provincesclass Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
int provinces = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
provinces++;
visited[i] = true;
Deque<Integer> q = new ArrayDeque<>();
q.offer(i);
while (!q.isEmpty()) {
int u = q.poll();
for (int v = 0; v < n; v++) {
if (isConnected[u][v] == 1 && !visited[v]) {
visited[v] = true;
q.offer(v);
}
}
}
}
return provinces;
}
}class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<bool> visited(n, false);
int provinces = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) continue;
provinces++;
visited[i] = true;
queue<int> q;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 0; v < n; v++) {
if (isConnected[u][v] == 1 && !visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
return provinces;
}
};func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
visited := make([]bool, n)
provinces := 0
for i := 0; i < n; i++ {
if visited[i] {
continue
}
provinces++
visited[i] = true
q := []int{i}
for len(q) > 0 {
u := q[0]
q = q[1:]
for v := 0; v < n; v++ {
if isConnected[u][v] == 1 && !visited[v] {
visited[v] = true
q = append(q, v)
}
}
}
}
return provinces
}var findCircleNum = function(isConnected) {
const n = isConnected.length;
const visited = new Array(n).fill(false);
let provinces = 0;
for (let i = 0; i < n; i++) {
if (visited[i]) continue;
provinces++;
visited[i] = true;
const q = [i];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (let v = 0; v < n; v++) {
if (isConnected[u][v] === 1 && !visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
return provinces;
};function findCircleNum(isConnected: number[][]): number {
const n = isConnected.length;
const visited = new Array(n).fill(false);
let provinces = 0;
for (let i = 0; i < n; i++) {
if (visited[i]) continue;
provinces++;
visited[i] = true;
const q = [i];
for (let h = 0; h < q.length; h++) {
const u = q[h];
for (let v = 0; v < n; v++) {
if (isConnected[u][v] === 1 && !visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
}
return provinces;
}解法 3：并查集 时间 O(n²·α(n))，空间 O(n)
每个城市先自成一个集合，省份数初始为 n。枚举邻接矩阵上三角中的每条连边 (i, j)，用带路径压缩的 find 找到两个城市的根。根不同就合并两个集合，省份数减一。α 为反阿克曼函数，可视为常数。
不需要搜索，只处理边。边是逐条给出或会动态增加时，并查集比搜索更合适。
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
n = len(isConnected)
parent = list(range(n))
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
provinces = n
for i in range(n):
for j in range(i + 1, n):
if isConnected[i][j] == 1:
a, b = find(i), find(j)
if a != b:
parent[a] = b
provinces -= 1
return provincesclass Solution {
int[] parent;
int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
parent = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int provinces = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
int a = find(i), b = find(j);
if (a != b) {
parent[a] = b;
provinces--;
}
}
}
}
return provinces;
}
}class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
vector<int> parent(n);
for (int i = 0; i < n; i++) parent[i] = i;
auto find = [&](int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
int provinces = n;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (isConnected[i][j] == 1) {
int a = find(i), b = find(j);
if (a != b) {
parent[a] = b;
provinces--;
}
}
}
}
return provinces;
}
};func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
parent := make([]int, n)
for i := range parent {
parent[i] = i
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
provinces := n
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
if isConnected[i][j] == 1 {
a, b := find(i), find(j)
if a != b {
parent[a] = b
provinces--
}
}
}
}
return provinces
}var findCircleNum = function(isConnected) {
const n = isConnected.length;
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x) => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let provinces = n;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isConnected[i][j] === 1) {
const a = find(i), b = find(j);
if (a !== b) {
parent[a] = b;
provinces--;
}
}
}
}
return provinces;
};function findCircleNum(isConnected: number[][]): number {
const n = isConnected.length;
const parent = Array.from({ length: n }, (_, i) => i);
const find = (x: number): number => {
while (parent[x] !== x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
};
let provinces = n;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
if (isConnected[i][j] === 1) {
const a = find(i), b = find(j);
if (a !== b) {
parent[a] = b;
provinces--;
}
}
}
}
return provinces;
}