6191. 好路径的数目 并查集

6191. 好路径的数目

给你一棵 n 个节点的树（连通无向无环的图），节点编号从 0 到 n - 1 且恰好有 n - 1 条边。

给你一个长度为 n 下标从 0 开始的整数数组 vals ，分别表示每个节点的值。同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 无向 边。

一条 好路径 需要满足以下条件：

1. 开始节点和结束节点的值 相同 。
2. 开始节点和结束节点中间的所有节点值都 小于等于 开始节点的值（也就是说开始节点的值应该是路径上所有节点的最大值）。

请你返回不同好路径的数目。

注意，一条路径和它反向的路径算作 同一 路径。比方说， 0 -> 1 与 1 -> 0 视为同一条路径。单个节点也视为一条合法路径。

示例 1：

输入：vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
输出：6
解释：总共有 5 条单个节点的好路径。
还有 1 条好路径：1 -> 0 -> 2 -> 4 。
（反方向的路径 4 -> 2 -> 0 -> 1 视为跟 1 -> 0 -> 2 -> 4 一样的路径）
注意 0 -> 2 -> 3 不是一条好路径，因为 vals[2] > vals[0] 。

示例 2：

输入：vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
输出：7
解释：总共有 5 条单个节点的好路径。
还有 2 条好路径：0 -> 1 和 2 -> 3 。

示例 3：

输入：vals = [1], edges = []
输出：1
解释：这棵树只有一个节点，所以只有一条好路径。

提示：

• n == vals.length
• 1 <= n <= 3 * 104
• 0 <= vals[i] <= 105
• edges.length == n - 1
• edges[i].length == 2
• 0 <= ai, bi < n
• ai != bi
• edges 表示一棵合法的树。

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

做题结果

失败，第一步就写错了，DFS硬解。这题的评价是，不但要会用并查集，还要会两个关键点的处理才能解出来。

方法：并查集

参考题解：并查集（Python/Java/C++/Go）

通过这题才知道并查集也可以用来求局部最大，最小，各种最，并可以对其进行计数。

1. 建图，这个要注意是无向边，a->b,b->a都要加入邻接表

2. 点排序，从小的点排到大的点。这个处理是因为删除无效路径，没有添加有效路径快，我们从小值路径加到大值路径，再处理后面的部分

3. 并查集，初始父节点都是自己，大小为0（注意这里大小指的是并查集同一group最大值相等的值得数目）

4. 按点逐一加入边。这个并查集需要特殊处理，每个group取最大值作为根节点。对于一条边的两点，a和b,他们的最大值分别为ra(a的根节点)，rb(b的根节点)，注意只有val[ra]>val[rb]，才要处理，因为较大值处理前，可能还可以加入其他有效边，不能提前处理。另外，如果a和b已经链接了（比如两个点的值相同），那就不能重复计算。

5. 对于两个不同的group根节点 ra,rb,他们对应得到根节点相同的值 size[ra]和size[rb]。分别代表两块不同的group中的值x的数目，任意两个可以相连形成路径，那么答案需要累计两者的乘积。

6. 后续需要把两块合成一块（小和等都可合成，但是只有相等才可改变size大小）。

class Solution {
        int[] parent;
        int[] sizes;
        public int numberOfGoodPaths(int[] vals, int[][] edges) {
            int n = vals.length;
            Set[] graph = new HashSet[n];
            Arrays.setAll(graph,o->new HashSet<>());
            for(int[] edge:edges){
                int u = edge[0];
                int v = edge[1];
                graph[u].add(v);
                graph[v].add(u);
            }
            parent = new int[n];
            sizes = new int[n];
            for(int i =0 ; i < n; i++) {
                parent[i] = i;
                sizes[i] = 1;
            }
 
            Integer []sort = new Integer[n];
            for(int i = 0; i < n; i++) sort[i] = i;
            Arrays.sort(sort,(a,b)->vals[a]-vals[b]);
            int ans = n;
            for(int a:sort){
                int ra = root(a);
                for(int b:graph[a]){
                    int rb = root(b);
                    if(vals[rb]>vals[ra] || ra == rb) continue;
                    if(vals[rb]==vals[ra]){
                        ans += sizes[ra]*sizes[rb];
                        sizes[ra]+=sizes[rb];
                    }
                    parent[rb] = ra;
                }
            }
            return ans;
        }
 
        private int root(int a){
            while (parent[a]!=a){
                parent[a] = parent[parent[a]];
                a = parent[a];
            }
            return a;
        }
    }