python3 解法, 执行用时: 120 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-20 17:33:59

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        cities = len(isConnected)
        visited = set()
        provinces = 0
        
        for i in range(cities):
            if i not in visited:
                Q = collections.deque([i])
                while Q:
                    j = Q.popleft()
                    visited.add(j)
                    for k in range(cities):
                        if isConnected[j][k] == 1 and k not in visited:
                            Q.append(k)
                provinces += 1
        
        return provinces

python3 解法, 执行用时: 40 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-20 17:33:47

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def find(index: int) -> int:
            if parent[index] != index:
                parent[index] = find(parent[index])
            return parent[index]
        
        def union(index1: int, index2: int):
            parent[find(index1)] = find(index2)
        
        cities = len(isConnected)
        parent = list(range(cities))
        
        for i in range(cities):
            for j in range(i + 1, cities):
                if isConnected[i][j] == 1:
                    union(i, j)
        
        provinces = sum(parent[i] == i for i in range(cities))
        return provinces

golang 解法, 执行用时: 20 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-20 17:33:31

// 并查集
func findCircleNum(isConnected [][]int) (ans int) {
    n := len(isConnected)
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        if parent[x] != x {
            parent[x] = find(parent[x])
        }
        return parent[x]
    }
    union := func(from, to int) {
        parent[find(from)] = find(to)
    }

    for i, row := range isConnected {
        for j := i + 1; j < n; j++ {
            if row[j] == 1 {
                union(i, j)
            }
        }
    }
    for i, p := range parent {
        if i == p {
            ans++
        }
    }
    return
}

golang 解法, 执行用时: 16 ms, 内存消耗: 6.5 MB, 提交时间: 2022-11-20 17:33:07

func findCircleNum(isConnected [][]int) (ans int) {
    vis := make([]bool, len(isConnected))
    for i, v := range vis {
        if !v {
            ans++
            queue := []int{i}
            for len(queue) > 0 {
                from := queue[0]
                queue = queue[1:]
                vis[from] = true
                for to, conn := range isConnected[from] {
                    if conn == 1 && !vis[to] {
                        queue = append(queue, to)
                    }
                }
            }
        }
    }
    return
}

golang 解法, 执行用时: 20 ms, 内存消耗: 6.4 MB, 提交时间: 2022-11-20 17:32:50

// 深度优先搜索
func findCircleNum(isConnected [][]int) (ans int) {
    vis := make([]bool, len(isConnected))
    var dfs func(int)
    dfs = func(from int) {
        vis[from] = true
        for to, conn := range isConnected[from] {
            if conn == 1 && !vis[to] {
                dfs(to)
            }
        }
    }
    for i, v := range vis {
        if !v {
            ans++
            dfs(i)
        }
    }
    return
}

python3 解法, 执行用时: 52 ms, 内存消耗: 15.6 MB, 提交时间: 2022-11-20 17:32:03

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        def dfs(i: int):
            for j in range(cities):
                if isConnected[i][j] == 1 and j not in visited:
                    visited.add(j)
                    dfs(j)
        
        cities = len(isConnected)
        visited = set()
        provinces = 0

        for i in range(cities):
            if i not in visited:
                dfs(i)
                provinces += 1
        
        return provinces