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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    var dfs func(id int)
    dfs = func(id int) {
        visited[id] = true
        for nxt, connected := range isConnected[id] {
            if connected == 1 && !visited[nxt] {
                dfs(nxt)
            }
        }
    }
    ans := 0
    for id := 0; id < n; id++ {
        if !visited[id] {
            ans++
            dfs(id)
        }
    }
    return ans
}

解法二：BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    visited := make([]bool, n)
    ans := 0
    for id := 0; id < n; id++ {
        if !visited[id] {
            ans++
            visited[id] = true
            var queue []int
            queue = append(queue, id)
            for len(queue) > 0 {
                cur := queue[0]
                queue = queue[1:]
                for nxt, connected := range isConnected[cur] {
                    if connected == 1 && !visited[nxt] {
                        visited[nxt] = true
                        queue = append(queue, nxt)
                    }
                }
            }
        }
    }
    return ans
}

解法三：并查集

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51


type UnionFind struct {
    parent []int
}

func (uf *UnionFind) Init(n int) {
    uf.parent = make([]int, n)
    for i := 0; i < len(uf.parent); i++ {
        uf.parent[i] = i
    }
}

// Count 返回并查集中有几个不相交的集合
func (uf *UnionFind) Count() int {
    ans := 0
    for i := 0; i < len(uf.parent); i++ {
        if uf.parent[i] == i {
            ans++
        }
    }
    return ans
}

// Merge 合并包含 i 的集合和包含 j 的集合
func (uf *UnionFind) Merge(i, j int) {
    iF, jF := uf.Find(i), uf.Find(j)
    if iF != jF {
        uf.parent[iF] = jF
    }
}

// Find 查询 i 的祖先（root）
func (uf *UnionFind) Find(i int) int {
    if uf.parent[i] != i {
        uf.parent[i] = uf.Find(uf.parent[i])
    }
    return uf.parent[i]
}

func findCircleNum(isConnected [][]int) int {
    n := len(isConnected)
    uf := &UnionFind{}
    uf.Init(n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if isConnected[i][j] == 1 {
                uf.Merge(i, j)
            }
        }
    }
    return uf.Count()
}