547. 省份數量

描述

有 n 個城市，其中一些彼此相連，另一些沒有相連。如果城市 a 與城市 b 直接相連，且城市 b 與城市 c 直接相連，那么城市 a 與城市 c 間接相連。

省份 是一組直接或間接相連的城市，組內不含其他沒有相連的城市。

給你一個 n x n 的矩陣 isConnected ，其中 isConnected[i][j] = 1 表示第 i 個城市和第 j 個城市直接相連，而 isConnected[i][j] = 0 表示二者不直接相連。

返回矩陣中 省份 的數量。

示例 1

輸入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
輸出：2

示例 2

輸入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
輸出：3

提示

• 1 <= n <= 200
• n == isConnected.length
• n == isConnected[i].length
• isConnected[i][j] 為 1 或 0
• isConnected[i][i] == 1
• isConnected[i][j] == isConnected[j][i]

解題思路

核心分析

這道題是一個經典的圖論連通性問題。核心思想是計算無向圖中連通分量的數量。

問題本質：給定一個無向圖的鄰接矩陣，計算圖中連通分量的個數。

關鍵洞察：

• 每個城市是一個節點，城市間的連接關系構成邊
• 省份就是連通分量，即相互可達的節點集合
• 可以通過遍歷算法（DFS/BFS）或并查集來求解

問題轉化

原始問題：計算n個城市中省份的數量

圖論轉化：

1. 將城市抽象為圖中的節點
2. 將城市間的連接關系抽象為圖中的邊
3. 省份數量 = 連通分量數量

數學建模：

• 節點集合：V = {0, 1, 2, …, n-1}
• 邊集合：E = {(i, j) | isConnected[i][j] = 1}
• 目標：計算圖G(V, E)中連通分量的數量

算法選擇策略

1. 深度優先搜索 (DFS)

• 適用場景：連通性問題，需要遍歷所有可達節點
• 優勢：實現簡單，遞歸清晰，空間效率高
• 劣勢：可能棧溢出，不適合極大數據量

2. 廣度優先搜索 (BFS)

• 適用場景：連通性問題，需要層次遍歷
• 優勢：避免棧溢出，適合大數據量
• 劣勢：需要隊列空間，實現稍復雜

3. 并查集 (Union-Find)

• 適用場景：動態連通性問題，需要頻繁合并操作
• 優勢：支持動態操作，理論復雜度最優
• 劣勢：實現復雜，常數項較大

算法實現詳解

方法一：深度優先搜索 (DFS)

核心思想：從每個未訪問的節點開始，遞歸訪問所有可達節點

算法步驟：

1. 初始化訪問數組visited，記錄每個節點是否被訪問
2. 遍歷所有節點，對每個未訪問的節點：
   • 調用DFS函數訪問該節點及其所有可達節點
   • 連通分量數量加1
3. DFS函數實現：
   • 標記當前節點為已訪問
   • 遍歷所有與當前節點相連的節點
   • 對每個未訪問的相連節點遞歸調用DFS

代碼實現：

func findCircleNumDFS(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}visited := make([]bool, n)count := 0for i := 0; i < n; i++ {if !visited[i] {dfs(isConnected, visited, i)count++}}return count
}func dfs(isConnected [][]int, visited []bool, city int) {visited[city] = truefor nextCity := 0; nextCity < len(isConnected); nextCity++ {if isConnected[city][nextCity] == 1 && !visited[nextCity] {dfs(isConnected, visited, nextCity)}}
}

時間復雜度分析：

• 每個節點最多被訪問一次：O(n)
• 每次訪問需要遍歷所有相鄰節點：O(n)
• 總時間復雜度：O(n2)

空間復雜度分析：

• 訪問數組：O(n)
• 遞歸調用棧深度：O(n)
• 總空間復雜度：O(n)

方法二：廣度優先搜索 (BFS)

核心思想：使用隊列進行層次遍歷，訪問所有可達節點

算法步驟：

1. 初始化訪問數組和隊列
2. 遍歷所有節點，對每個未訪問的節點：
   • 將節點加入隊列
   • 標記為已訪問
   • 連通分量數量加1
   • 執行BFS遍歷
3. BFS函數實現：
   • 從隊列中取出節點
   • 遍歷所有與當前節點相連的節點
   • 將未訪問的相連節點加入隊列并標記為已訪問

代碼實現：

func findCircleNumBFS(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}visited := make([]bool, n)count := 0for i := 0; i < n; i++ {if !visited[i] {bfs(isConnected, visited, i)count++}}return count
}func bfs(isConnected [][]int, visited []bool, startCity int) {queue := []int{startCity}visited[startCity] = truefor len(queue) > 0 {city := queue[0]queue = queue[1:]for nextCity := 0; nextCity < len(isConnected); nextCity++ {if isConnected[city][nextCity] == 1 && !visited[nextCity] {visited[nextCity] = truequeue = append(queue, nextCity)}}}
}

時間復雜度：O(n2)
空間復雜度：O(n)

方法三：并查集 (Union-Find)

核心思想：使用并查集維護連通性，通過合并操作統計連通分量

算法步驟：

1. 初始化并查集，每個節點自成一個集合
2. 遍歷鄰接矩陣，對每個連接關系：
   • 合并相連的兩個節點到同一集合
3. 統計最終集合的數量

并查集優化：

• 路徑壓縮：在查找時壓縮路徑，減少后續查找時間
• 按秩合并：將較小的樹合并到較大的樹上，保持樹的平衡

代碼實現：

type UnionFind struct {parent []intrank   []intcount  int
}func NewUnionFind(n int) *UnionFind {parent := make([]int, n)rank := make([]int, n)for i := 0; i < n; i++ {parent[i] = irank[i] = 1}return &UnionFind{parent: parent,rank:   rank,count:  n,}
}func (uf *UnionFind) Find(x int) int {if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x]) // 路徑壓縮}return uf.parent[x]
}func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)if rootX == rootY {return}// 按秩合并if uf.rank[rootX] < uf.rank[rootY] {uf.parent[rootX] = rootY} else if uf.rank[rootX] > uf.rank[rootY] {uf.parent[rootY] = rootX} else {uf.parent[rootY] = rootXuf.rank[rootX]++}uf.count--
}func (uf *UnionFind) Count() int {return uf.count
}

時間復雜度：O(n2 × α(n))，其中α(n)是阿克曼函數的反函數
空間復雜度：O(n)

算法選擇

1. 深度優先搜索 (DFS)

• 時間復雜度：O(n2)，其中 n 是城市數量
• 空間復雜度：O(n)，遞歸調用棧的深度
• 適用場景：適合處理連通性問題

2. 廣度優先搜索 (BFS)

• 時間復雜度：O(n2)
• 空間復雜度：O(n)，隊列的空間
• 適用場景：適合處理連通性問題，避免遞歸棧溢出

3. 并查集 (Union-Find)

• 時間復雜度：O(n2 × α(n))，其中 α(n) 是阿克曼函數的反函數
• 空間復雜度：O(n)
• 適用場景：適合處理動態連通性問題

數學證明

并查集正確性證明

定理：并查集算法能正確計算連通分量的數量。

證明：

1. 初始化正確性：

   • 初始時每個節點自成一個集合
   • 集合數量等于節點數量

2. 合并操作正確性：

   • 每次合并操作將兩個連通分量合并為一個
   • 集合數量減少1

3. 最終結果正確性：

   • 所有相連的節點都在同一集合中
   • 不同連通分量的節點在不同集合中
   • 集合數量等于連通分量數量

時間復雜度分析

定理：并查集算法的時間復雜度為O(n2 × α(n))。

證明：

• 每個節點最多參與n次合并操作
• 每次合并操作的時間復雜度為O(α(n))
• 總時間復雜度為O(n2 × α(n))

執行流程圖

算法可視化

實際應用

1. 社交網絡分析：計算朋友圈的數量
2. 網絡拓撲分析：計算網絡中的連通區域
3. 地理信息系統：計算地理區域的連通性
4. 電路設計：分析電路的連通性
5. 生物信息學：分析蛋白質相互作用網絡

算法優化技巧

1. 內存優化

// 使用位運算優化訪問數組
visited := make([]uint64, (n+63)/64)

2. 早期終止

// 如果所有節點都已訪問，可以提前終止
if count == n {return 1
}

3. 對稱性利用

// 利用鄰接矩陣的對稱性，只遍歷上三角
for i := 0; i < n; i++ {for j := i + 1; j < n; j++ {if isConnected[i][j] == 1 {// 處理連接關系}}
}

擴展思考

1. 有向圖：如果是有向圖，如何計算強連通分量？
2. 加權圖：如果邊有權重，如何定義連通性？
3. 動態圖：如果圖結構動態變化，如何維護連通性？
4. 大規模圖：對于超大規模圖，如何優化算法？
5. 并行算法：如何設計并行版本的連通分量算法？

相關問題

1. 200. 島嶼數量：二維網格中的連通分量問題
2. 130. 被圍繞的區域：連通分量的邊界處理
3. 399. 除法求值：帶權圖的連通性問題
4. 684. 冗余連接：并查集在最小生成樹中的應用
5. 685. 冗余連接 II：有向圖的連通性問題

測試用例設計

// 基礎測試用例
isConnected1 := [][]int{{1, 1, 0},{1, 1, 0},{0, 0, 1},
}
expected1 := 2isConnected2 := [][]int{{1, 0, 0},{0, 1, 0},{0, 0, 1},
}
expected2 := 3// 邊界測試
isConnected3 := [][]int{{1}}
expected3 := 1var isConnected4 [][]int
expected4 := 0// 極值測試
isConnected5 := [][]int{{1, 1, 1},{1, 1, 1},{1, 1, 1},
}
expected5 := 1// 復雜情況
isConnected6 := [][]int{{1, 0, 0, 1},{0, 1, 1, 0},{0, 1, 1, 1},{1, 0, 1, 1},
}
expected6 := 1

性能對比

算法	時間復雜度	空間復雜度	常數項	適用場景
DFS	O(n2)	O(n)	小	一般情況
BFS	O(n2)	O(n)	中等	大數據量
并查集	O(n2 × α(n))	O(n)	大	動態連通性

常見錯誤

1. 訪問標記錯誤：忘記標記節點為已訪問
2. 遞歸終止錯誤：遞歸函數沒有正確的終止條件
3. 數組越界：訪問鄰接矩陣時越界
4. 并查集初始化錯誤：parent數組初始化不正確
5. 邊界處理錯誤：沒有正確處理空矩陣或單個節點

總結

省份數量 是一道經典的圖論連通性問題，核心在于理解連通分量的概念和計算算法。

最優解法是DFS或BFS算法，具有以下優勢：

1. 時間復雜度合理：O(n2)
2. 實現簡單：遞歸或隊列遍歷
3. 空間效率高：只需要O(n)額外空間
4. 應用廣泛：是圖遍歷的經典模板題

這道題體現了圖論算法中的重要思想：

• 連通性分析：通過遍歷確定節點間的可達性
• 訪問標記：避免重復訪問，提高算法效率
• 問題建模：將實際問題抽象為圖論問題

并查集算法雖然理論復雜度最優，但在實際應用中，由于常數項較大，對于中等規模的問題，DFS/BFS算法往往更實用。

算法流程圖

詳細解題步驟

方法一：深度優先搜索 (DFS)

1. 初始化：創建訪問數組 visited，記錄每個城市是否被訪問過
2. 遍歷城市：從每個未訪問的城市開始進行DFS
3. DFS過程：
   • 標記當前城市為已訪問
   • 遍歷所有與當前城市相連的城市
   • 對每個未訪問的相連城市遞歸調用DFS
4. 計數：每次開始新的DFS時，省份數量加1

方法二：廣度優先搜索 (BFS)

1. 初始化：創建訪問數組和隊列
2. 遍歷城市：從每個未訪問的城市開始進行BFS
3. BFS過程：
   • 將當前城市加入隊列
   • 標記為已訪問
   • 從隊列中取出城市，遍歷其所有相連城市
   • 將未訪問的相連城市加入隊列
4. 計數：每次開始新的BFS時，省份數量加1

方法三：并查集 (Union-Find)

1. 初始化：創建并查集，每個城市自成一個集合
2. 合并操作：遍歷鄰接矩陣，將相連的城市合并到同一集合
3. 統計集合：統計最終有多少個不同的集合

復雜度分析

方法	時間復雜度	空間復雜度	優勢	劣勢
DFS	O(n2)	O(n)	實現簡單，遞歸清晰	可能棧溢出
BFS	O(n2)	O(n)	避免棧溢出	需要隊列
并查集	O(n2 × α(n))	O(n)	適合動態連通性	實現復雜

邊界情況處理

1. 空矩陣：返回0
2. 單個城市：返回1
3. 所有城市都不相連：返回n
4. 所有城市都相連：返回1

優化技巧

1. 提前返回：如果所有城市都已訪問，可以提前結束
2. 對稱性利用：由于是無向圖，鄰接矩陣是對稱的
3. 內存優化：使用位運算優化訪問數組的存儲

完整題解代碼

package mainimport ("fmt"
)// 方法一：深度優先搜索 (DFS)
// 時間復雜度：O(n2)，空間復雜度：O(n)
func findCircleNumDFS(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}// 訪問數組，記錄每個城市是否被訪問過visited := make([]bool, n)count := 0// 從每個未訪問的城市開始DFSfor i := 0; i < n; i++ {if !visited[i] {dfs(isConnected, visited, i)count++}}return count
}// DFS輔助函數
func dfs(isConnected [][]int, visited []bool, city int) {visited[city] = true// 遍歷所有與當前城市相連的城市for nextCity := 0; nextCity < len(isConnected); nextCity++ {if isConnected[city][nextCity] == 1 && !visited[nextCity] {dfs(isConnected, visited, nextCity)}}
}// 方法二：廣度優先搜索 (BFS)
// 時間復雜度：O(n2)，空間復雜度：O(n)
func findCircleNumBFS(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}visited := make([]bool, n)count := 0// 從每個未訪問的城市開始BFSfor i := 0; i < n; i++ {if !visited[i] {bfs(isConnected, visited, i)count++}}return count
}// BFS輔助函數
func bfs(isConnected [][]int, visited []bool, startCity int) {queue := []int{startCity}visited[startCity] = truefor len(queue) > 0 {city := queue[0]queue = queue[1:]// 遍歷所有與當前城市相連的城市for nextCity := 0; nextCity < len(isConnected); nextCity++ {if isConnected[city][nextCity] == 1 && !visited[nextCity] {visited[nextCity] = truequeue = append(queue, nextCity)}}}
}// 方法三：并查集 (Union-Find)
// 時間復雜度：O(n2 × α(n))，空間復雜度：O(n)
func findCircleNumUnionFind(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}// 初始化并查集uf := NewUnionFind(n)// 遍歷鄰接矩陣，合并相連的城市for i := 0; i < n; i++ {for j := i + 1; j < n; j++ { // 利用對稱性，只遍歷上三角if isConnected[i][j] == 1 {uf.Union(i, j)}}}return uf.Count()
}// 并查集結構
type UnionFind struct {parent []intrank   []intcount  int
}// 創建新的并查集
func NewUnionFind(n int) *UnionFind {parent := make([]int, n)rank := make([]int, n)for i := 0; i < n; i++ {parent[i] = irank[i] = 1}return &UnionFind{parent: parent,rank:   rank,count:  n,}
}// 查找根節點（路徑壓縮）
func (uf *UnionFind) Find(x int) int {if uf.parent[x] != x {uf.parent[x] = uf.Find(uf.parent[x]) // 路徑壓縮}return uf.parent[x]
}// 合并兩個集合（按秩合并）
func (uf *UnionFind) Union(x, y int) {rootX := uf.Find(x)rootY := uf.Find(y)if rootX == rootY {return}// 按秩合并if uf.rank[rootX] < uf.rank[rootY] {uf.parent[rootX] = rootY} else if uf.rank[rootX] > uf.rank[rootY] {uf.parent[rootY] = rootX} else {uf.parent[rootY] = rootXuf.rank[rootX]++}uf.count--
}// 返回集合數量
func (uf *UnionFind) Count() int {return uf.count
}// 方法四：優化的DFS（使用棧避免遞歸）
// 時間復雜度：O(n2)，空間復雜度：O(n)
func findCircleNumDFSIterative(isConnected [][]int) int {n := len(isConnected)if n == 0 {return 0}visited := make([]bool, n)count := 0for i := 0; i < n; i++ {if !visited[i] {dfsIterative(isConnected, visited, i)count++}}return count
}// 迭代式DFS
func dfsIterative(isConnected [][]int, visited []bool, startCity int) {stack := []int{startCity}visited[startCity] = truefor len(stack) > 0 {city := stack[len(stack)-1]stack = stack[:len(stack)-1]for nextCity := 0; nextCity < len(isConnected); nextCity++ {if isConnected[city][nextCity] == 1 && !visited[nextCity] {visited[nextCity] = truestack = append(stack, nextCity)}}}
}// 測試函數
func main() {// 測試用例1：示例1isConnected1 := [][]int{{1, 1, 0},{1, 1, 0},{0, 0, 1},}fmt.Println("測試用例1:")fmt.Printf("輸入: %v\n", isConnected1)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected1))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected1))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected1))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected1))fmt.Println("期望結果: 2")fmt.Println()// 測試用例2：示例2isConnected2 := [][]int{{1, 0, 0},{0, 1, 0},{0, 0, 1},}fmt.Println("測試用例2:")fmt.Printf("輸入: %v\n", isConnected2)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected2))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected2))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected2))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected2))fmt.Println("期望結果: 3")fmt.Println()// 測試用例3：所有城市相連isConnected3 := [][]int{{1, 1, 1},{1, 1, 1},{1, 1, 1},}fmt.Println("測試用例3 (所有城市相連):")fmt.Printf("輸入: %v\n", isConnected3)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected3))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected3))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected3))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected3))fmt.Println("期望結果: 1")fmt.Println()// 測試用例4：單個城市isConnected4 := [][]int{{1}}fmt.Println("測試用例4 (單個城市):")fmt.Printf("輸入: %v\n", isConnected4)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected4))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected4))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected4))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected4))fmt.Println("期望結果: 1")fmt.Println()// 測試用例5：空矩陣var isConnected5 [][]intfmt.Println("測試用例5 (空矩陣):")fmt.Printf("輸入: %v\n", isConnected5)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected5))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected5))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected5))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected5))fmt.Println("期望結果: 0")fmt.Println()// 測試用例6：復雜情況isConnected6 := [][]int{{1, 0, 0, 1},{0, 1, 1, 0},{0, 1, 1, 1},{1, 0, 1, 1},}fmt.Println("測試用例6 (復雜情況):")fmt.Printf("輸入: %v\n", isConnected6)fmt.Printf("DFS結果: %d\n", findCircleNumDFS(isConnected6))fmt.Printf("BFS結果: %d\n", findCircleNumBFS(isConnected6))fmt.Printf("并查集結果: %d\n", findCircleNumUnionFind(isConnected6))fmt.Printf("迭代DFS結果: %d\n", findCircleNumDFSIterative(isConnected6))fmt.Println("期望結果: 1")
}