并查集模板总结

并查集（Union-find Data Structure）是一种树型的数据结构。它的特点是由子结点找到父亲结点，用于处理一些不交集（Disjoint Sets）的合并及查询问题。
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。

模板一(子节点指向祖先节点)

子节点指向祖先节点

type unionFind struct {
	ancestor []int
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
	}
	return &unionFind{
		ancestor: uf,
	}
}

//带路径压缩的查找
func (uf *unionFind) find(node int) int {
	for uf.ancestor[node] != node {
		uf.ancestor[node] = uf.ancestor[uf.ancestor[node]]
		node = uf.ancestor[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		uf.ancestor[root2] = root1
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}

（见例题1）

模板二(统计连通区域内的元素个数)

统计连通区域内的元素个数

type unionFind struct {
	father []int
	size   []int //size[i] 表示以 i 为根的集合中元素个数
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	sz := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
		sz[i] = 1
	}
	return &unionFind{
		father: uf,
		size:   sz,
	}
}

func (uf *unionFind) find(node int) int {
	for uf.father[node] != node {
		node = uf.father[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		if uf.size[root2] <= uf.size[root1] {
			uf.father[root2] = root1
			uf.size[root1] += uf.size[root2]
		} else {
			uf.father[root1] = root2
			uf.size[root2] += uf.size[root1]
		}
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}

（见例题2）

模板三(统计连通分量的个数)

统计连通分量的个数

type unionFind struct {
	ancestor []int
	count    int   //连通分量的个数
}

func (uf *unionFind) getCount() int {
	return uf.count
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
	}
	return &unionFind{
		ancestor: uf,
		count: totalNodes,
	}
}

//带路径压缩的查找
func (uf *unionFind) find(node int) int {
	for uf.ancestor[node] != node {
		uf.ancestor[node] = uf.ancestor[uf.ancestor[node]]
		node = uf.ancestor[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		uf.ancestor[root2] = root1
		uf.count--
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}

(见例题3)

模板四(带权并查集)

带权并查集（不常用）
（参考力扣399. 除法求值）

    fa := make([]int, len(id))
    w := make([]float64, len(id))  //权值，根据题目定义进行调整更改
    for i := range fa {
        fa[i] = i
        w[i] = 1
    }
    var find func(int) int
    find = func(x int) int {
        if fa[x] != x {
            f := find(fa[x])
            w[x] *= w[fa[x]]
            fa[x] = f
        }
        return fa[x]
    }
    union:= func(from, to int, val float64) {
        fFrom, fTo := find(from), find(to)
        w[fFrom] = val * w[to] / w[from]
        fa[fFrom] = fTo
    }

例题1

力扣990. 等式方程的可满足性

现根据相等关系建立并查集，然后根据不等关系检验并查集中的连接是否合理，直接使用模板一即可。

func equationsPossible(equations []string) bool {
	uf := UnionFind(26)
	n := len(equations)
	var id = func(c byte)int{
		return int(c)-97
	}
	for i := 0; i < n; i++ {
		if equations[i][1] == '='{
			uf.union(id(equations[i][0]),id(equations[i][3]))
		}
	}
	for i := 0; i < n; i++ {
		if equations[i][1] == '!'{
			if uf.isConnected(id(equations[i][0]),id(equations[i][3])){
				return false
			}
		}
	}
	return true
}

type unionFind struct {
	ancestor []int
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
	}
	return &unionFind{
		ancestor: uf,
	}
}

//带路径压缩的查找
func (uf *unionFind) find(node int) int {
	for uf.ancestor[node] != node {
		uf.ancestor[node] = uf.ancestor[uf.ancestor[node]]
		node = uf.ancestor[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		uf.ancestor[root2] = root1
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}

例题2

力扣1020. 飞地的数量


把相邻的1组成一个连通分量，统计所有1的个数cnt，再统计外圈的连通分量内有多少个1(记为count)，用cnt-count即为被水(0)包围的1的个数

func numEnclaves(grid [][]int) int {
	rows, cols := len(grid), len(grid[0])
	size := rows * cols
	uf := UnionFind(size + 1)
    //将二维坐标转变为一维索引
	id := func(a, b int) int {
		return a*cols + b
	}
    //统计所有1的个数
	cnt := 0
	for i := 0; i < rows; i++ {
		for j := 0; j < cols; j++ {
			if grid[i][j] == 1 {
				cnt++
			}
		}
	}
    //第一行和最后一行的1加入外圈的连通分量中
	for i := 0; i < cols; i++ {
		if grid[0][i] == 1 {
			uf.union(size, i)
		}
		if grid[rows-1][i] == 1 {
			uf.union(size, id(rows-1, i))
		}
	}
    //第一列和最后一列的1加入外圈的连通分量中
	for i := 1; i < rows-1; i++ {
		if grid[i][0] == 1 {
			uf.union(size, id(i, 0))
		}
		if grid[i][cols-1] == 1 {
			uf.union(size, id(i, cols-1))
		}
	}
    //找内圈的1，并和四个方向的1进行union
	directions := [4][2]int{{0, 1}, {1, 0}, {-1, 0}, {0, -1}}
	for i := 1; i < rows-1; i++ {
		for j := 1; j < cols-1; j++ {
			if grid[i][j] == 1 {
				for k := 0; k < 4; k++ {
					x,y := i+directions[k][0],j+directions[k][1]
					if grid[x][y] == 1 {
						uf.union(id(x,y), id(i,j))
					}
				}
			}
		}
	}

//找到根节点，size下标表示的节点一定是外圈的节点，因此从size开始往上找根，并在最后把这个虚拟的size节点给删掉
	return cnt - uf.size[uf.find(size)] + 1
}


type unionFind struct {
	father []int
	size   []int //size[i] 表示以 i 为根的集合中元素个数
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	sz := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
		sz[i] = 1
	}
	return &unionFind{
		father: uf,
		size:   sz,
	}
}

func (uf *unionFind) find(node int) int {
	for uf.father[node] != node {
		node = uf.father[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		if uf.size[root2] <= uf.size[root1] {
			uf.father[root2] = root1
			uf.size[root1] += uf.size[root2]
		} else {
			uf.father[root1] = root2
			uf.size[root2] += uf.size[root1]
		}
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}

例题3

力扣765. 情侣牵手

考虑这样一个连通分量，连同分量里的人都能找到对应的情侣，且连同分量是不可再细分的，(假设Aa为情侣，则连通分量可以是ABaCcb。但是不可以是ABbaCdDc，因为它可以被细分为ABba和CdDc两个连通分量)
对于每一个有n对情侣的连通分量，只需要交换n-1次就可以让情侣挨着坐（少于n-1次就说明可以细分连通分量了，配对前面n-1对情侣最多需要n-1次，配对完后最后一对情侣自然配对）。
因此可以使用模板三来统计连通分量的个数，计算出最少需要的交换次数

func minSwapsCouples(row []int) int {
	n := len(row)
	l := n>>1
	uf := UnionFind(l)
	for i := 0; i < n; i+=2 {
		uf.union(row[i]/2,row[i+1]/2)  //注意情侣表示的元素是一样的，比如0/2=0，1/2=0
	}
    //假设个连通分量内的元素数目分别为n1,n2,...,nk，则有n1+n2+...+nk = l
    //则需要交换的次数为n1-1,n2-1,...,nk-1，把这k个数加起来则等于l-k
	return l-uf.getCount()
}

type unionFind struct {
	ancestor []int
	count    int   //连通分量的个数
}

func (uf *unionFind) getCount() int {
	return uf.count
}

func UnionFind(totalNodes int) *unionFind {
	uf := make([]int, totalNodes)
	for i := 0; i < totalNodes; i++ {
		uf[i] = i
	}
	return &unionFind{
		ancestor: uf,
		count: totalNodes,
	}
}

//带路径压缩的查找
func (uf *unionFind) find(node int) int {
	for uf.ancestor[node] != node {
		uf.ancestor[node] = uf.ancestor[uf.ancestor[node]]
		node = uf.ancestor[node]
	}
	return node
}

func (uf *unionFind) union(node1, node2 int) {
	root1, root2 := uf.find(node1), uf.find(node2)
	if root1 != root2 {
		uf.ancestor[root2] = root1
		uf.count--
	}
}

func (uf *unionFind) isConnected(node1, node2 int) bool {
	return uf.find(node1) == uf.find(node2)
}