[TOC]

基础知识

https://labuladong.gitee.io/algo/2/22/53/

https://leetcode.cn/circle/discuss/qmjuMW/

B站上古城算法讲的也很不错；

并查集是一种树形的数据结构，用于处理不交集的合并（union）和查询（find）问题

Find：确认元素属于哪一个子集，确认两个元素是不是同一个子集

Union：将两个子集合并为同一个集合

找到root parent，也就是根父母

比如：

TreeNode1 := TreeNode{Val:3,Left:  &TreeNode{1, nil, nil},Right: &TreeNode{2,nil, nil }}
3是root，3的parent=3，1和2的parent=3

TreeNode2 := TreeNode{Val:4,Left:  &TreeNode{5, nil, nil},Right: nil}
4是root，4的parent=4，5的parent=4

union(1,5)=> 找到1的root parent=3，找到5的root parent=4, 也就是3做4的孩子，或者3做4的父母，都可以，合并两个子集。

基础模板伪代码

初始化

func makeSet(x)
  x.parent=x

查询

func Find(x)
 if x.parent==x{return x}
 else return Find(x.parent)

合并（找到root parent，然后其中一个root parent做另外一个的kid）

func Union(x,y)
  xRoot:=Find(x)
  yRoot:=Find(y)
  x.Root.parent=yRoot

基础模板

type UF struct {
    count  int
    parent []int
}

// 并查集模板
func NewUF(x int) *UF {
    u := UF{
        count:  x,  
        parent: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
    }
    return &u
}

// 查询,找root parent
func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 合并普通版
func (u *UF) Union_simple(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

// (可选)判断两个节点有没有连接
func (u *UF) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

//（可选），其实一般都直接是u.count
func (u *UF) Count() int {
    return u.count
}

//（可选）
func (u *UF) Add() {
    u.count++
}

weight优化模板

type UF_weight struct {
    count  int
    parent []int
    weight []int
}

// 并查集模板
func NewUF_weight(x int) *UF_weight {
    u := UF_weight{
        count:  x, 
        parent: make([]int, x),
        weight: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
        u.weight[i] = 1
    }
    return &u
}

// 查询,找root parent
func (u *UF_weight) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 合并优化版，利用weight
func (u *UF_weight) Union_weight(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    if u.weight[rootA] < u.weight[rootB] {
        u.parent[rootA] = rootB
        u.weight[rootB] += u.weight[rootA]
    } else {
        u.parent[rootB] = rootA
        u.weight[rootA] += u.weight[rootB]
    }
    u.count--
}

//（可选）判断两个节点有没有连接
func (u *UF_weight) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

//（可选）
func (u *UF_weight) Count() int {
    return u.count
}

//（可选）
func (u *UF_weight) Add() {
    u.count++
}

rank优化模板

type UF_rank struct {
    count  int
    parent []int
    rank []int
}

// 并查集模板
func NewUF_rank(x int) *UF_rank {
    u := UF_rank{
        count:  x,  
        parent: make([]int, x),
        rank: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
        u.rank[i] = 1
    }
    return &u
}

// 查询,找root parent
func (u *UF_rank) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

 
// 合并优化版，利用rank
func (u *UF_rank) Union_rank(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    if u.rank[rootA] < u.rank[rootB] {
        u.parent[rootA] = rootB
    } else if u.rank[rootA] > u.rank[rootB] {
        u.parent[rootB] = rootA
    } else { // 只有rank相等的情况下合并后才需要维护rank，rank需要+1
        u.parent[rootA] = rootB
        u.rank[rootB]++
    }
    u.count--
}


// （可选）判断两个节点有没有连接
func (u *UF_rank) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

//（可选）
func (u *UF_rank) Count() int {
    return u.count
}

//（可选）
func (u *UF_rank) Add() {
    u.count++
}

字符串模板（可参考737题）

// ======================= 以下这个模板也比较经典，是和string有关的（注意要记住）  =========================
type UF struct {
    count  int
    parent map[string]string
}

func NewUF(x int, sentence1 []string, sentence2 []string) *UF {
    u := UF{
        count:  x,
        parent: make(map[string]string, x),  //这个是核心
    }
    for i := 0; i < x; i++ {
        u.parent[sentence1[i]] = sentence1[i]
        u.parent[sentence2[i]] = sentence2[i]
    }
    return &u
}

func (u *UF) Find(x string) string {
    if strings.Compare(u.parent[x], x) != 0 { // u.parent[x]==x,strings.Compare结果=0
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b string) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

func (u *UF) Connected(a, b string) bool {
    return u.Find(a) == u.Find(b)
}

Leetcode刷题

323. 无向图中连通分量的数目（会员/中等）

你有一个包含 n 个节点的图。给定一个整数 n 和一个数组 edges ，其中 edges[i] = [ai, bi] 表示图中 ai 和 bi 之间有一条边。
返回 图中已连接分量的数目 。
输入: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
输出: 2

输入: n = 5, edges = [[0,1], [1,2], [2,3], [3,4]]
输出:  1

func main() {
    n := 5
    edges := [][]int{{0, 1}, {1, 2}, {3, 4}}
    fmt.Println(countComponents(n, edges))
}

func countComponents(n int, edges [][]int) int {
    obj := NewUF(n)
    for _, v := range edges {
        obj.Union(v[0], v[1])
    }
    return obj.count
}

type UF struct {
    parent []int
    count  int
}

func NewUF(x int) *UF {
    parent := make([]int, x)
    for i := 0; i < x; i++ {
        parent[i] = i
    }
    count := x
    return &UF{parent: parent, count: count}
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b int) {
    rootA := u.Find(a)
    rootB := u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

547. 省份数量（中等）

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

// 这一题很明显需要用并查集来做，而不是利用200题岛屿数量的DFS来套用，虽然可以用DFS来解题，但是需要变化。
func findCircleNum(isConnected [][]int) (ans int) {
    n := len(isConnected)
    obj := NewUF(n)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if isConnected[i][j] == 1 {
                obj.Union_simple(i, j)
            }
        }
    }
    return obj.count
}

type UF struct {
    count  int
    parent []int
}

// 并查集模板
func NewUF(x int) *UF {
    u := UF{
        count:  x, // 与模板不一样的地方：初始没有岛屿(题目要求初始都是海)
        parent: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
    }
    return &u
}

// 查询,找root parent
func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 合并普通版
func (u *UF) Union_simple(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

305. 岛屿数量 II(会员/困难)

给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 grid 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
- 操作 #1：addLand(0, 0) 将 grid[0][0] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #2：addLand(0, 1) 将 grid[0][1] 的水变为陆地。此时存在 1 个岛屿。
- 操作 #3：addLand(1, 2) 将 grid[1][2] 的水变为陆地。此时存在 2 个岛屿。
- 操作 #4：addLand(2, 1) 将 grid[2][1] 的水变为陆地。此时存在 3 个岛屿。

[图片上传失败...(image-943ace-1671479296836)]

func main() {
    m := 3
    n := 3
    positions1 := [][]int{{0, 0}, {0, 1}, {1, 2}, {2, 1}}
    fmt.Println(numIslands2_personal(m, n, positions1))

    positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
    fmt.Println(numIslands2_personal(m, n, positions2))

}

func numIslands2_personal(m int, n int, positions [][]int) []int {
    u := NewUF(m * n) // 构造函数
    grid := make([][]int, m)
    for i := 0; i < m; i++ {
        grid[i] = make([]int, n)
    }

    var res []int
    var inGrid = func(x, y int) bool {
        return x >= 0 && y >= 0 && x < m && y < n
    }

    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}
    for _, p := range positions {
        x, y := p[0], p[1]
        index := x*n + y // 用 index=x∗n+y 表示 (x,y) 这个点。

        // 这一段用来干嘛的，主要是判断输入有没有重复的，重复的可以直接返回结果，比如 positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
        if grid[x][y] == 1 {
            res = append(res, u.Count())
            continue
        }

        grid[x][y] = 1 // 填岛屿了
        u.Add()

        for _, v := range dirs {
            newRow := x + v[0]
            newCol := y + v[1]
            Index := newRow*n + newCol
            if inGrid(newRow, newCol) && grid[newRow][newCol] == 1 && !u.Connected(index, Index) { // 如果其中一个方向有已经填过的岛屿，且没有连接在一起,那么就可以将填海位置与已经填过的岛屿连接在一起，同时孤岛数量-1(在Union里面自动做掉)
                u.Union_weight(index, Index)
            }
        }
        res = append(res, u.Count())
    }
    return res
}

func numIslands2(m int, n int, positions [][]int) []int {
    u := NewUF(m * n)            // 构造函数
    visited := make([]bool, m*n) // 二维变一维，这里最精髓的地方就是二维问题转化为一维问题
    var res []int

    var inGrid = func(x, y int) bool {
        return x >= 0 && y >= 0 && x < m && y < n
    }

    dirs := [][]int{{0, 1}, {0, -1}, {1, 0}, {-1, 0}}

    for _, p := range positions {
        x, y := p[0], p[1]
        index := x*n + y // 用 index=x∗n+y 表示 (x,y) 这个点。

        // 这一段用来干嘛的，主要是判断输入有没有重复的，重复的可以直接返回结果，比如 positions2 := [][]int{{0, 0}, {0, 1}, {1, 2}, {1, 2}}
        if visited[index] {
            res = append(res, u.Count())
            continue
        }

        visited[index] = true // 填岛屿
        u.Add()

        for _, v := range dirs {
            newRow := x + v[0]
            newCol := y + v[1]
            Index := newRow*n + newCol
            if inGrid(newRow, newCol) && visited[Index] && !u.Connected(index, Index) { // 如果其中一个方向有已经填过的岛屿，且没有连接在一起,那么就可以将填海位置与已经填过的岛屿连接在一起，同时孤岛数量-1(在Union里面自动做掉)
                u.Union_weight(index, Index)
            }
        }
        res = append(res, u.Count())
    }
    return res
}

// ============  以下是并查集模板  =========================
type UF struct {
    count  int
    parent []int
    weight []int
}

// 并查集模板
func NewUF(x int) *UF {
    u := UF{
        count:  0, // 与模板不一样的地方：初始没有岛屿(题目要求初始都是海)，这里初始化需要注意下 
        parent: make([]int, x),
        weight: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
        u.weight[i] = 1  // 这里初始化的weight也要注意，是1，不是i
    }
    return &u
}

// 查询,找root parent
func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 合并优化版，利用weight
func (u *UF) Union_weight(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    if u.weight[rootA] < u.weight[rootB] {
        u.parent[rootA] = rootB
        u.weight[rootB] += u.weight[rootA]
    } else {
        u.parent[rootB] = rootA
        u.weight[rootA] += u.weight[rootB]
    }
    u.count--
}

// 判断两个节点有没有连接
func (u *UF) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

func (u *UF) Count() int {
    return u.count
}

func (u *UF) Add() {
    u.count++
}

1101. 彼此熟识的最早时间（会员/中等）

在一个社交圈子当中，有 n 个人。每个人都有一个从 0 到 n - 1 的唯一编号。我们有一份日志列表 logs，其中 logs[i] = [timestampi, xi, yi] 表示 xi 和 yi 将在同一时间 timestampi 成为朋友。友谊是相互的。也就是说，如果 a 和 b 是朋友，那么 b 和 a 也是朋友。同样，如果 a 和 b 是朋友，或者 a 是 b 朋友的朋友 ，那么 a 和 b 是熟识友。返回圈子里所有人之间都熟识的最早时间。如果找不到最早时间，就返回 -1 。

输入：logs = [[20190101,0,1],[20190104,3,4],[20190107,2,3],[20190211,1,5],[20190224,2,4],[20190301,0,3],[20190312,1,2],[20190322,4,5]], N = 6
输出：20190301
解释：
第一次结交发生在 timestamp = 20190101，0 和 1 成为好友，社交朋友圈如下 [0,1], [2], [3], [4], [5]。
第二次结交发生在 timestamp = 20190104，3 和 4 成为好友，社交朋友圈如下 [0,1], [2], [3,4], [5].
第三次结交发生在 timestamp = 20190107，2 和 3 成为好友，社交朋友圈如下 [0,1], [2,3,4], [5].
第四次结交发生在 timestamp = 20190211，1 和 5 成为好友，社交朋友圈如下 [0,1,5], [2,3,4].
第五次结交发生在 timestamp = 20190224，2 和 4 已经是好友了。
第六次结交发生在 timestamp = 20190301，0 和 3 成为好友，大家都互相熟识了。

输入: logs = [[0,2,0],[1,0,1],[3,0,3],[4,1,2],[7,3,1]], n = 4
输出: 3

func main() {
    logs := [][]int{
        {20190101, 0, 1},
        {20190104, 3, 4},
        {20190107, 2, 3},
        {20190211, 1, 5},
        {20190224, 2, 4},
        {20190301, 0, 3},
        {20190312, 1, 2},
        {20190322, 4, 5}}
    N := 6
    fmt.Println(earliestAcq(logs, N))

    logs1 := [][]int{{9, 3, 0}, {0, 2, 1}, {8, 0, 1}, {1, 3, 2}, {2, 2, 0}, {3, 3, 1}}
    N1 := 4
    fmt.Println(earliestAcq(logs1, N1))
}

func earliestAcq(logs [][]int, n int) int {
    obj := NewUF(n)
    sort.Slice(logs, func(i, j int) bool { // 这里按照第一列进行排序非常重要，因为不一定时间先的放在数组前面了
        return logs[i][0] < logs[j][0]
    })

    fmt.Println(logs)

    for _, v := range logs {
        obj.Union(v[1], v[2])
        if obj.count == 1 {
            return v[0]
        }
    }
    return -1
}

type UF struct {
    parent []int
    count  int
}

func NewUF(x int) *UF {
    parent := make([]int, x)
    for i := 0; i < x; i++ {
        parent[i] = i
    }
    count := x
    return &UF{parent: parent, count: count}
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b int) {
    rootA := u.Find(a)
    rootB := u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

1135. 最低成本联通所有城市（会员/中等）

想象一下你是个城市基建规划者，地图上有 n 座城市，它们按以 1 到 n 的次序编号。给你整数 n 和一个数组 conections，其中 connections[i] = [xi, yi, costi] 表示将城市 xi 和城市 yi 连接所要的costi（连接是双向的）。返回连接所有城市的最低成本，每对城市之间至少有一条路径。如果无法连接所有 n 个城市，返回 -1. 该 最小成本 应该是所用全部连接成本的总和。

输入：n = 3, conections = [[1,2,5],[1,3,6],[2,3,1]]
输出：6
解释：选出任意 2 条边都可以连接所有城市，我们从中选取成本最小的 2 条。

输入：n = 4, conections = [[1,2,3],[3,4,4]]
输出：-1
解释：即使连通所有的边，也无法连接所有城市。

func main() {
    n := 3
    conections := [][]int{{1, 2, 5}, {1, 3, 6}, {2, 3, 1}}
    fmt.Println(minimumCost(n, conections))
}

func minimumCost(n int, connections [][]int) int {
    obj := NewUF(n + 1) // 这里需要注意的是城市是从1开始的，也就是三个城市，1，2，3，必须要+1，避免panic.
    sort.Slice(connections, func(i, j int) bool { // 这里按照第一列进行排序非常重要，因为不一定时间先的放在数组前面了
        return connections[i][2] < connections[j][2]
    })

    fmt.Println(connections)
    res := 0
    for _, v := range connections {
        if !obj.Connected(v[0], v[1]) {  // 其实这里还有一点贪心算法的意思，如果不连，就连通。不能无脑连通，有可能之前已经是连通状态了
            obj.Union(v[0], v[1])
            res += v[2]
        }

        if obj.count == 2 { // 这里需要注意的是城市是从1开始的，也就是三个城市，1，2，3  
            return res
        }
    }
    return -1
}

type UF struct {
    parent []int
    count  int
}

func NewUF(x int) *UF {
    parent := make([]int, x)
    for i := 0; i < x; i++ {
        parent[i] = i
    }
    count := x
    return &UF{parent: parent, count: count}
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b int) {
    rootA := u.Find(a)
    rootB := u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

func (uf *UF) Connected(a, b int) bool {
    return uf.Find(a) == uf.Find(b)
}

1061. 按字典序排列最小的等效字符串（会员/中等）

给出长度相同的两个字符串s1 和 s2 ，还有一个字符串 baseStr 。其中  s1[i] 和 s2[i]  是一组等价字符。举个例子，如果 s1 = "abc" 且 s2 = "cde"，那么就有 'a' == 'c', 'b' == 'd', 'c' == 'e'。
等价字符遵循任何等价关系的一般规则：
自反性 ：'a' == 'a'
对称性 ：'a' == 'b' 则必定有 'b' == 'a'
传递性 ：'a' == 'b' 且 'b' == 'c' 就表明 'a' == 'c'
例如， s1 = "abc" 和 s2 = "cde" 的等价信息和之前的例子一样，那么 baseStr = "eed" , "acd" 或 "aab"，这三个字符串都是等价的，而 "aab" 是 baseStr 的按字典序最小的等价字符串. 利用 s1 和 s2 的等价信息，找出并返回 baseStr 的按字典序排列最小的等价字符串。

输入：s1 = "parker", s2 = "morris", baseStr = "parser"
输出："makkek"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。

输入：s1 = "hello", s2 = "world", baseStr = "hold"
输出："hdld"
解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。

输入：s1 = "leetcode", s2 = "programs", baseStr = "sourcecode"
输出："aauaaaaada"
解释：我们可以把 A 和 B 中的等价字符分为 [a,o,e,r,s,c], [l,p], [g,t] 和 [d,m] 共 4 组，因此 S 中除了 'u' 和 'd' 之外的所有字母都转化成了 'a'，最后答案为 "aauaaaaada"。

func main() {
    s1 := "parker"
    s2 := "morris"
    baseStr := "parser"
    fmt.Println(smallestEquivalentString(s1, s2, baseStr))
}
// 这个思路有点绝啊，将字符转化为数字
func smallestEquivalentString(s1 string, s2 string, baseStr string) string {
    s1Len := len(s1)
    obj := NewUF(26) // 这里非常关键，为什么是26呢。因为是字母，最多26个需要找父节点
    for i := 0; i < s1Len; i++ {
        obj.Union(int(s1[i]-'a'), int(s2[i]-'a'))
    }

    res := []byte{}
    for i := range baseStr {
        res = append(res, byte('a'+obj.Find(int(baseStr[i]-'a'))))
    }
    return string(res)
}

// 模板
type UF struct {
    count  int
    parent []int
}

func NewUF(x int) *UF {
    u := UF{
        count:  x,
        parent: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
    }
    return &u
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

// 此题在这里最基础的模板针对题目进行了优化，也就是要找最小的parent
func (u *UF) Union(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    if rootA < rootB { // 为了找最小的parent
        u.parent[rootB] = rootA
    } else {
        u.parent[rootA] = rootB
    }
    u.count--
}

func (u *UF) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

1102. 得分最高的路径（会员/中等）

给定一个 m x n 的整数矩阵 grid，返回从 (0,0) 开始到 (m - 1, n - 1) 在四个基本方向上移动的路径的最大 分数 。一条路径的 分数 是该路径上的最小值。例如，路径 8 → 4 → 5 → 9 的得分为 4 。

输入：grid = [[5,4,5],[1,2,6],[7,4,6]]
输出：4
解释：得分最高的路径用黄色突出显示。 

输入：grid = [[2,2,1,2,2,2],[1,2,2,2,1,2]]
输出：2

输入：grid = [[3,4,6,3,4],[0,2,1,1,7],[8,8,3,2,7],[3,2,4,9,8],[4,1,2,0,0],[4,6,5,4,3]]
输出：3

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/path-with-maximum-minimum-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

[图片上传失败...(image-388dda-1671479296836)]

// ================== 解法一： 并查集  =====================
// 这里其实很关键，就相当于从大到小挨个中，后来看是不是能连通
// 1. 把节点值 从大到小 逐个尝试，直到最后拼出来grid[0,0]到grid[row-1, col-1](从左上角到右下角)的通路。
// 2. 进行UF，期间记录最小值
// 2. 如果最后通了，那么返回res
func maximumMinimumPath(grid [][]int) int {
    row, col := len(grid), len(grid[0])
    array := make([][]int, 0)
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            temp := []int{i, j, grid[i][j]}
            array = append(array, temp)
        }
    }

    fmt.Println(array)

    sort.Slice(array, func(i, j int) bool { // 按照二维数组的值从大到小排列
        return array[i][2] > array[j][2]
    })
    

    obj := NewUF(row * col)
    
    visited := make([]bool, row*col)
    visited[0] = true
    visited[row*col-1] = true
    
    res := min(grid[0][0], grid[row-1][col-1])
    directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
    
    for _, node := range array {
        x, y := node[0], node[1]
        index := x*col + y
        res = min(res, node[2])
        visited[index] = true
        for _, dir := range directions {
            newX := x + dir[0]
            newY := y + dir[1]
            newIndex := newX*col + newY
            if newX >= 0 && newX < row && newY >= 0 && newY < col && visited[newIndex] {
                obj.Union(index, newIndex)
            }
    
            if obj.Connected(0, row*col-1) { // 左上和右下连通了,退出
                return res
            }
        }
    }
    return res

}

// 模板
type UF struct {
    count  int
    parent []int
}

func NewUF(x int) *UF {
    u := UF{
        count:  x,
        parent: make([]int, x),
    }
    for i := 0; i < x; i++ {
        u.parent[i] = i
    }
    return &u
}

func (u *UF) Find(x int) int {
    if u.parent[x] != x {
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b int) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

func (u *UF) Connected(a, b int) bool {
    return u.Find(a) == u.Find(b)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

====================  上述是利用数组的，也可以转化为node结构体来   ====================
type node struct {
    value int
    row   int
    col   int
}

func maximumMinimumPath(grid [][]int) int {
    row, col := len(grid), len(grid[0])
    obj := NewUF(row * col)

    var nodes []node
    for i := 0; i < row; i++ {
        for j := 0; j < col; j++ {
            nodes = append(nodes, node{value: grid[i][j], row: i, col: j})
        }
    }
    sort.Slice(nodes, func(i, j int) bool { // 按照二维数组的值从大到小排列
        return nodes[i].value > nodes[j].value
    })

    fmt.Println(nodes)

    visited := make([]bool, row*col)
    visited[0] = true
    visited[row*col-1] = true

    res := min(grid[0][0], grid[row-1][col-1])
    directions := [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

    for _, node := range nodes {
        x, y := node.row, node.col
        index := x*col + y
        res = min(res, node.value)
        visited[index] = true
        for _, dir := range directions {
            newX := x + dir[0]
            newY := y + dir[1]
            newIndex := newX*col + newY
            if newX >= 0 && newX < row && newY >= 0 && newY < col && visited[newIndex] {
                obj.Union(index, newIndex)
            }
            
            if obj.Connected(0, row*col-1) { // 左上和右下连通了,退出
                return res
            }
        }
    }
    return res

}

261. 以图判树（会员/中等）

给定编号从 0 到 n - 1 的 n 个结点。给定一个整数 n 和一个 edges 列表，其中 edges[i] = [ai, bi] 表示图中节点 ai 和 bi 之间存在一条无向边。如果这些边能够形成一个合法有效的树结构，则返回 true ，否则返回 false 。

输入: n = 5, edges = [[0,1],[0,2],[0,3],[1,4]]
输出: true

输入: n = 5, edges = [[0,1],[1,2],[2,3],[1,3],[1,4]]
输出: false

func main() {
    n := 5
    edges := [][]int{{0, 1}, {0, 2}, {0, 3}, {1, 4}}
    fmt.Println(validTree(n, edges))

    edge2 := [][]int{{0, 1}, {1, 2}, {2, 3}, {1, 3}, {1, 4}} // 1,2,3形成了一个环，所以会挂。
    fmt.Println(validTree(n, edge2))
}

func validTree(n int, edges [][]int) bool {
    obj := NewUF(n)
    for _, v := range edges {
        if obj.Connected(v[0], v[1]) { // 如何判断没有环，就是判断有没有连通，比如一开始有[0 1] [0 2], 此时如果来[1 2]，12已经是连通的，那就成环了。
            return false
        }
        obj.Union(v[0], v[1])
    }
    return obj.count==1
}

734. 句子相似性（会员/简单）

我们可以将一个句子表示为一个单词数组，例如，句子 "I am happy with leetcode" 可以表示为 arr = ["I","am",happy","with","leetcode"]. 给定两个句子 sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi and yi 是相似的。如果 sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。
两个句子是相似的，如果:它们具有 相同的长度 (即相同的字数)sentence1[i] 和 sentence2[i] 是相似的. 请注意，一个词总是与它自己相似，也请注意，相似关系是不可传递的。例如，如果单词 a 和 b 是相似的，单词 b 和 c 也是相似的，那么 a 和 c  不一定相似 。

输入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","fine"],["drama","acting"],["skills","talent"]]
输出: true
解释: 这两个句子长度相同，每个单词都相似。

输入: sentence1 = ["great"], sentence2 = ["great"], similarPairs = []
输出: true
解释: 一个单词和它本身相似。

输入: sentence1 = ["great"], sentence2 = ["doubleplus","good"], similarPairs = [["great","doubleplus"]]
输出: false
解释: 因为它们长度不同，所以返回false。

// 此题需要注意，不是一对一的关系，是多对多，比如：["brunch","meal"],["breakfast","meal"],["food","meal"]，多对多，其实就不方便用map[string]string{}了。最简单的场景，没用到任何算法。
func areSentencesSimilar(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
    if len(sentence1) != len(sentence2){
        return false
    }
    wordSet := map[string]int{}
    for _, v := range similarPairs{
        str := v[0]+"#"+v[1]  // 中间加一个#，真的是很机智了。
        wordSet[str]++
    }

    for i, v1 := range sentence1{
        v2 :=sentence2[i]
        if v1 != v2 && wordSet[v1+"#"+v2] == 0 && wordSet[v2+"#"+v1] == 0 {
            return false
        }
    }

    return true
}

737. 句子相似性 II（会员/中等）

我们可以将一个句子表示为一个单词数组，例如，句子 I am happy with leetcode"可以表示为 arr = ["I","am",happy","with","leetcode"]

给定两个句子 sentence1 和 sentence2 分别表示为一个字符串数组，并给定一个字符串对 similarPairs ，其中 similarPairs[i] = [xi, yi] 表示两个单词 xi 和 yi 是相似的。

如果 sentence1 和 sentence2 相似则返回 true ，如果不相似则返回 false 。

两个句子是相似的，如果:

它们具有 相同的长度 (即相同的字数)
sentence1[i] 和 sentence2[i] 是相似的
请注意，一个词总是与它自己相似，也请注意，相似关系是可传递的。例如，如果单词 a 和 b 是相似的，单词 b 和 c 也是相似的，那么 a 和 c 也是 相似 的。

输入: sentence1 = ["great","acting","skills"], sentence2 = ["fine","drama","talent"], similarPairs = [["great","good"],["fine","good"],["drama","acting"],["skills","talent"]]
输出: true
解释: 这两个句子长度相同，每个单词都相似。

输入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","onepiece"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
输出: true
解释: "leetcode" --> "platform" --> "anime" --> "manga" --> "onepiece".
因为“leetcode”和“onepiece”相似，而且前两个单词是相同的，所以这两句话是相似的。

输入: sentence1 = ["I","love","leetcode"], sentence2 = ["I","love","onepiece"], similarPairs = [["manga","hunterXhunter"],["platform","anime"],["leetcode","platform"],["anime","manga"]]
输出: false
解释: “leetcode”和“onepiece”不相似。

func main() {
    sentence1 := []string{"great", "acting", "skills"}
    sentence2 := []string{"fine", "drama", "talent"}
    similarPairs := [][]string{{"great", "fine"}, {"drama", "acting"}, {"skills", "talent"}}
    fmt.Println(areSentencesSimilarTwo(sentence1, sentence2, similarPairs))

    sentence11 := []string{"I", "love", "leetcode"}
    sentence22 := []string{"I", "love", "onepiece"}
    similarPairs2 := [][]string{{"manga", "onepiece"}, {"platform", "anime"}, {"leetcode", "platform"}, {"anime", "manga"}}
    fmt.Println(areSentencesSimilarTwo(sentence11, sentence22, similarPairs2))
}

func areSentencesSimilarTwo(sentence1 []string, sentence2 []string, similarPairs [][]string) bool {
    sen1Len, sen2Len := len(sentence1), len(sentence2)
    if sen1Len != sen2Len {
        return false
    }
    obj := NewUF(sen1Len, sentence1, sentence2)

    for _, v := range similarPairs {
        obj.Union(v[0], v[1])
    }

    flag := true

    //word1 和 word2一一对应查并查集， 如果有一个不是相似的，则flag = false
    for i := 0; i < sen1Len; i++ {
        if obj.Find(sentence1[i]) != obj.Find(sentence2[i]) {
            flag = false
        }
    }
    return flag
}

// ======================= 以下这个模板也比较经典，是和string有关的（注意要记住）  =========================
type UF struct {
    count  int
    parent map[string]string
}

func NewUF(x int, sentence1 []string, sentence2 []string) *UF {
    u := UF{
        count:  x,
        parent: make(map[string]string, x),  //这个是核心
    }
    for i := 0; i < x; i++ {
        u.parent[sentence1[i]] = sentence1[i]
        u.parent[sentence2[i]] = sentence2[i]
    }
    return &u
}

func (u *UF) Find(x string) string {
    if strings.Compare(u.parent[x], x) != 0 { // u.parent[x]==x,strings.Compare结果=0
        u.parent[x] = u.Find(u.parent[x])
    }
    return u.parent[x]
}

func (u *UF) Union(a, b string) {
    rootA, rootB := u.Find(a), u.Find(b)
    if rootA == rootB {
        return
    }
    u.parent[rootA] = rootB
    u.count--
}

func (u *UF) Connected(a, b string) bool {
    return u.Find(a) == u.Find(b)
}

934. 最短的桥（中等）

给你一个大小为 n x n 的二元矩阵 grid ，其中 1 表示陆地，0 表示水域。岛 是由四面相连的 1 形成的一个最大组，即不会与非组内的任何其他 1 相连。grid 中 恰好存在两座岛 。你可以将任意数量的 0 变为 1 ，以使两座岛连接起来，变成 一座岛 。返回必须翻转的 0 的最小数目。

输入：grid = [[0,1],[1,0]]
输出：1

输入：grid = [[0,1,0],[0,0,0],[0,0,1]]
输出：2

输入：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
输出：1

827. 最大人工岛（困难）

给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。返回执行此操作后，grid 中最大的岛屿面积是多少？岛屿 由一组上、下、左、右四个方向相连的 1 形成。

输入: grid = [[1, 0], [0, 1]]
输出: 3
解释: 将一格0变成1，最终连通两个小岛得到面积为 3 的岛屿。

输入: grid = [[1, 1], [1, 0]]
输出: 4
解释: 将一格0变成1，岛屿的面积扩大为 4。

输入: grid = [[1, 1], [1, 1]]
输出: 4
解释: 没有0可以让我们变成1，面积依然为 4。

684. 冗余连接（中等）

树可以看成是一个连通且 无环 的 无向 图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。

输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]

输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]

463. 岛屿的周长（简单）

给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

694. 不同岛屿的数量（会员/中等/有点难）

给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。

输入: grid = [[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
输出：1

输入: grid = [[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]
输出: 3

[图片上传失败...(image-40f795-1671479296836)]

924. 尽量减少恶意软件的传播（困难）

给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。 一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。

输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1]
输出：0

输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2]
输出：0

输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2]
输出：1