【LeetCode】547、省份数量
【LeetCode】547、省份数量
文章目录
- 一、并查集
- 1.1 并查集
- 二、多语言解法
一、并查集
1.1 并查集
初始时共n个集合, 若相邻则合并, 最终返回并查集的集合总数
// go
var sets int
var father [40000]int
func findCircleNum(isConnected [][]int) int {
n := len(isConnected)
build(isConnected)
for i := range n {
for j := i+1; j < n; j++ {
if isConnected[i][j] == 1 {
union(i,j)
}
}
}
return sets
}
func build(isConnected [][]int) {
n := len(isConnected)
for i := range n {
father[i]=i
}
sets = n
}
func find(i int) int {
if father[i] != i {
father[i] = find(father[i])
}
return father[i]
}
func union(a, b int) {
fa, fb := find(a), find(b)
if fa != fb {
father[fa] = fb
sets--
}
}
二、多语言解法
C p p / G o / P y t h o n / R u s t / J s / T s Cpp/Go/Python/Rust/Js/Ts Cpp/Go/Python/Rust/Js/Ts
// cpp
// go 同上
# python
// rust
// js
// ts