并查集

• 参考：https://blog.csdn.net/bjweimengshu/article/details/108332389
• https://zhuanlan.zhihu.com/p/93647900/

1、定义

• 并查集是一种树型的数据结构，用于处理一些不相交集合（disjoint sets）的合并及查询问题。常常在使用中以森林来表示。
• 并查集的思想是通过标记确定该顶点所在的组。
• 1、应用：判断一个图中两个点是否联通；分组问题
• 2、函数：初始化(init)、合并(Union)、查询(Find)
• 3、初始化（init）： 初始化一个N大小的数组，初始值为下标
• 4、合并（Union）：把两个不相交的集合合并为一个集合。
• 5、查询（Find）：查询两个元素是否在同一个集合中。使用递归实现，访问父节点，直至根节点。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

复杂度

2、实现

// 隔代路径压缩
func find(x int) int {
    for x != fa[x] {
        fa[x] = fa[fa[x]]
        x = fa[x]
    }
    return x
}
// 彻底路径压缩
func find(x int) int {
    if fa[x] != x {
        fa[x] = find(fa[x])
    }
    return fa[x]
}

不带秩

package main

import "fmt"

func main() {
    fa = Init(10)
    union(3, 1)
    union(1, 4)
    fmt.Println(find(3))
    fmt.Println(query(3, 4))
    fmt.Println(query(3, 5))
    fmt.Println(fa)
}

var fa []int

// Init 初始化
func Init(n int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    return arr
}

// 查询
func find(x int) int {
    if fa[x] != x {
        fa[x] = find(fa[x])
    }
    return fa[x]
}

// 合并
func union(i, j int) {
    fa[find(i)] = find(j)
}

func query(i, j int) bool {
    return find(i) == find(j)
}

带秩

package main

import "fmt"

func main() {
    fa, rank = Init(10)
    union(3, 1)
    union(1, 4)
    fmt.Println(find(3))
    fmt.Println(query(3, 4))
    fmt.Println(query(3, 5))
    fmt.Println(fa, rank)
}

var fa []int
var rank []int

// Init 初始化
func Init(n int) ([]int, []int) {
    arr := make([]int, n)
    r := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
        r[i] = 1
    }
    return arr, r
}

// 查询
func find(x int) int {
    if fa[x] == x {
        return x
    }
    // 路径压缩
    fa[x] = find(fa[x])
    return fa[x]
}

// 合并
func union(i, j int) {
    // 按秩合并
    x, y := find(i), find(j)
    if rank[x] <= rank[y] {
        fa[x] = y
    } else {
        fa[y] = x
    }
    if rank[x] == rank[y] && x != y {
        rank[y]++ // 如果深度相同且根节点不同，则新的根节点的深度+1
    }
}

func query(i, j int) bool {
    return find(i) == find(j)
}

map系列

package main

import (
    "fmt"
    "math"
)

func main() {
    fa = Init([]int{1, 3, 4, 6, 7, 8, 9, 10})
    fmt.Println(fa)
    union(3, 1)
    union(1, 4)
    fmt.Println(find(3))
    fmt.Println(query(3, 4))
    fmt.Println(query(3, 5))
}

var fa map[int]int

// Init 初始化
func Init(data []int) map[int]int {
    n := len(data)
    arr := make(map[int]int)
    for i := 0; i < n; i++ {
        arr[data[i]] = data[i]
    }
    return arr
}

// 查询
func find(x int) int {
    if _, ok := fa[x]; !ok {
        return math.MinInt32 // 特殊处理
    }
    res := x
    for res != fa[res] {
        res = fa[res]
    }
    return res
}

// 合并
func union(i, j int) {
    x, y := find(i), find(j)
    if x == y {
        return
    } else if x == math.MinInt32 || y == math.MinInt32 {
        return
    }
    fa[x] = y
}

func query(i, j int) bool {
    return find(i) == find(j)
}

带count

package main

import "fmt"

func main() {
    fa = Init(10)
    for i := 0; i < 10; i++ {
        if i%2 == 1 {
            count++
        }
    }
    union(3, 1)
    union(1, 4)
    fmt.Println(find(3))
    fmt.Println(query(3, 4))
    fmt.Println(query(3, 5))
    fmt.Println(fa)
}

var fa []int
var count int

// Init 初始化
func Init(n int) []int {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    count = n
    return arr
}

// 查询
func find(x int) int {
    if fa[x] == x {
        return x
    }
    // 路径压缩
    fa[x] = find(fa[x])
    return fa[x]
}

// 合并
func union(i, j int) {
    x, y := find(i), find(j)
    if x != y {
        fa[x] = y
        count--
    }
}

func query(i, j int) bool {
    return find(i) == find(j)
}

func getCount() int {
    return count
}

传参数

package main

import "fmt"

func main() {
    n := 200
    fa := make([]int, n)
    for i := 0; i < n; i++ {
        fa[i] = i
    }
    union(fa, 10, 20)
    union(fa, 10, 30)
    fmt.Println(find(fa, 20), find(fa, 30))
}

func union(fa []int, a, b int) {
    fa[find(fa, a)] = find(fa, b)
}

func find(fa []int, a int) int {
    for fa[a] != a {
        fa[a] = fa[fa[a]]
        a = fa[a]
    }
    return a
}

struct

package main

import "fmt"

func main() {
    a := &UnionFind{}
    a.Init(10)
    fmt.Println(a.count)
    fmt.Println(a.fa)
}

type UnionFind struct {
    fa    []int
    count int
}

// Init 初始化
func (u *UnionFind) Init(n int) {
    arr := make([]int, n)
    for i := 0; i < n; i++ {
        arr[i] = i
    }
    u.count = n
    u.fa = arr
}

// 查询
func (u UnionFind) find(x int) int {
    if u.fa[x] == x {
        return x
    }
    // 路径压缩
    u.fa[x] = u.find(u.fa[x])
    return u.fa[x]
}

// 合并
func (u *UnionFind) union(i, j int) {
    x, y := u.find(i), u.find(j)
    if x != y {
        u.fa[x] = y
        u.count--
    }
}

func (u UnionFind) query(i, j int) bool {
    return u.find(i) == u.find(j)
}

3、Leetcode

并查集不带权

并查集带权