题目

有 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]

注意：本题与主站 547 题相同：

解题思路分析

1、并查集；时间复杂度O(n^2)，空间复杂度O(n)

func findCircleNum(M [][]int) int {
   n := len(M)
   fa = Init(n)
   count = n
   for i := 0; i < n; i++ {
      for j := i + 1; j < n; j++ {
         if M[i][j] == 1 {
            union(i, j)
         }
      }
   }
   return getCount()
}

var fa []int
var count int

// 初始化
func Init(n int) []int {
   arr := make([]int, n)
   for i := 0; i < n; i++ {
      arr[i] = i
   }
   count = n
   return arr
}

// 查询
func find(x int) int {
   if fa[x] == x {
      return x
   }
   // 路径压缩
   fa[x] = find(fa[x])
   return fa[x]
}

// 合并
func union(i, j int) {
   x, y := find(i), find(j)
   if x != y {
      fa[x] = y
      count--
   }
}

func query(i, j int) bool {
   return find(i) == find(j)
}

func getCount() int {
   return count
}

2、递归；时间复杂度O(n^2)，空间复杂度O(n)

var arr []bool

func findCircleNum(M [][]int) int {
   n := len(M)
   arr = make([]bool, n)
   res := 0
   for i := 0; i < n; i++ {
      if arr[i] == false {
         dfs(M, i)
         res++
      }
   }
   return res
}

func dfs(M [][]int, index int) {
   for i := 0; i < len(M); i++ {
      if arr[i] == false && M[index][i] == 1 {
         arr[i] = true
         dfs(M, i)
      }
   }
}

3、广度优先搜索；时间复杂度O(n^2)，空间复杂度O(n)

func findCircleNum(M [][]int) int {
   n := len(M)
   arr := make([]bool, n)
   res := 0
   queue := make([]int, 0)
   for i := 0; i < n; i++ {
      if arr[i] == false {
         queue = append(queue, i)
         for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            arr[node] = true
            for j := 0; j < n; j++ {
               if M[node][j] == 1 && arr[j] == false {
                  queue = append(queue, j)
               }
            }
         }
         res++
      }
   }
   return res
}

总结

Medium题目，题目同leetcode 547. 省份数量