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]

---

解题分析及思路：

方法：并查集

思路：

利用并查集，将所有连通的节点合并

将每个节点的父节点设置为自身，然后遍历矩阵，如果两个节点相连，则将两个节点的父节点设置为相同的父节点。

最后统计父节点相同的数量（下标和父节点相同），即为省份数量。

func findCircleNum(isConnected [][]int) int {
	var parent = make([]int, len(isConnected))
	for index := range isConnected {
		parent[index] = index
	}
	var find func(num int) int
	find = func(num int) int {
		if parent[num] != num {
			parent[num] = find(parent[num])
		}
		return parent[num]
	}
	union := func(i, j int) {
		parent[find(j)] = find(i)
	}
	for i := range isConnected {
		for j := i + 1; j < len(isConnected[i]); j++ {
			if isConnected[i][j] == 1 {
				union(i, j)
			}
		}
	}
	var result int
	for index := range parent {
		if parent[index] == index {
			result++
		}
	}
	return result
}

复杂度：

• 时间复杂度：O(n² * log n)
• 空间复杂度：O(n² * log n)

执行结果：

• 执行耗时:19 ms,击败了40.64% 的Go用户
• 内存消耗:6.4 MB,击败了31.49% 的Go用户