广东佛山网站建设_西安小程序开发费用_产品如何做市场推广_营销助手

【LeetCode】547、省份数量

一、并查集

1.1 并查集

初始时共n个集合, 若相邻则合并, 最终返回并查集的集合总数

// go
var sets int
var father [40000]intfunc 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] = fbsets--}
}

二、多语言解法

$Cpp/Go/Python/Rust/Js/Ts$

// cpp

// go 同上

# python

// rust

// js

// ts