【LeetCode】2421、好路径的数目

【LeetCode】2421、好路径的数目

一、并查集

1.1 并查集

1.1.1 题意复述

有一个无向无环图, 每个节点有编号, 有值.
好路径是: 一条路径, 两端节点的值相同, 且大于中间节点的值, 的路径.
其中正反方向的好路径只算作一条; 单独一个节点也视为一条好路径.
求好路径的数目.

输入:

• 节点值的数组: 下标为节点编号, 值为节点值
• 边的数组 edges[]: 每项是 是一个长为2的数组, 是 一条边 的两侧节点

1.1.2 思路

1. 首先排序各 edges, 按 “边的两个节点的最大值” 谁小谁排在前面
2. build 并查集, 每个节点单独成集合, 每个集合记录代表节点, 和代表节点出现的次数
3. 按 排序后的 edges 顺序, union, 即合并 edge 两端的节点. 每次 union 会返回此次得到的好路径数量
   3.1 若 两个节点所在集团的 最大值相同, 则得到了好路径
   3.2 若 两个节点所在集团的 最大值不同, 则得不到好路径
4. 每遍历一个 edge, 得到一个好路径数目, 最终累加各好路径数目即可

核心思想是:

1. 因为 edges 按 “edge 两端节点的 最大值” 升序排序, 所以 统计的只是 edge 两边 “两个集团 各自的最大值”, 所以 得到的路径一定是好路径: 因为两端节点的值一定相同(因为判断时需值相同), 且中间节点的值一定小于两端节点的值(因为都是各自集团的max值).
2. 然后, 不断按顺序遍历 edges, 就不会遗漏了

// go
var father [30001]int // 用于维护 并查集 的链路关系, 存了 代表节点, 本题代表节点取集团内的最大值
var maxcnt [30001]int // 并查集 集合的 标签, 表示集合 代表节点(即集团内的最大值)出现的次数

func numberOfGoodPaths(vals []int, edges [][]int) int {
    slices.SortStableFunc(edges, func(a, b []int) int { // edge 两端节点的最大值 按升序排序
        // 注意 edge 两边的 a[0] a[1] 都是下标, 对应的值是 vals[a[0]] vals[a[1]]
        return cmp.Compare(max(vals[a[0]], vals[a[1]]), max(vals[b[0]], vals[b[1]]))
    })
    n := len(vals)
    build(n)
    ans := n // 单个节点 也算 好路径
    for _, e := range edges {
        ans += union(e[0], e[1], vals)
    }
    return ans
}

func build(n int) {
    for i := range n {
        father[i] = i // 初始化时, 集团内 代表节点就是自己
        maxcnt[i] = 1 // 初始化时, 集团内 代表节点出现了1次
    }
}

func find(i int) int {
    if father[i] != i {
        father[i] = find(father[i])
    }
    return father[i]
}

// a 和 b 是 edge 两端的两个节点
func union(a, b int, vals []int) (path int) {
    fa, fb := find(a), find(b) // fa 是 a 所在集团的代表节点, 也是a所在集团的最大值"下标"
    // if fa == fb {return} // 已为同一集团, 之前合并时肯定已计算过好路径了, 无需计算而返回
    if vals[fa] > vals[fb] { // "fa下标" 对应的 "节点值vals[fa]" 更大
        father[fb] = fa // 集团合并, 且推举fa为 合并后集团的代表节点
    } else if vals[fa] < vals[fb] {
        father[fa] = fb // 集团合并, 且推举fb为 合并后集团的代表节点
    } else { // 集团合并, 得到好路径, 且推举 fa或fb任意一个 为 合并后集团的代表节点 都行
        path = maxcnt[fa] * maxcnt[fb]
        father[fa] = fb // 例如推举fb为 合并后集团的代表节点
        maxcnt[fb] += maxcnt[fa]
    }
    return
}

参考 左神 并查集

二、多语言解法

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

// cpp

// go 同上

# python

// rust

// js

// ts