# 2421. Number of Good Paths
###### tags: `Leetcode` `Hard` `Union Find`
## 思路
先把所有nodes按照value分 然后按照value从小到大一组一组建图
再用所有edge建graph 对于一个点来说 它里面存的所有能到的点都要满足val<=它的val
对于每个新的node来说 我们要把他(用graph里面存的所有这个node能到达的并且val小于等于这个node的val的所有nodes)连在原先建的图(with nodes with smaller values)上面
然后根据每次新加的点是不是最后在同一个group(有同一个father)里面得到答案
因为如果一个group有两个新加的点就会多一条路径 如果一个group有三个新加的点就会多三条路径
## Code

class Solution {
    int[] fa;
    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        TreeMap<Integer, List<Integer>> sameVal = new TreeMap<>();
        List<List<Integer>> graph = new ArrayList<>();
        int n = vals.length;
        fa = new int[n];
        for(int i=0; i<n; i++) fa[i] = i;
        for(int i=0; i<n; i++) graph.add(new ArrayList<>());
        for(int i=0; i<n; i++){
            if(!sameVal.containsKey(vals[i])){
                sameVal.put(vals[i], new ArrayList<>());
            }
            sameVal.get(vals[i]).add(i);
        }
        for(int[] edge:edges){
            if(vals[edge[0]]>=vals[edge[1]]) graph.get(edge[0]).add(edge[1]);
            if(vals[edge[1]]>=vals[edge[0]]) graph.get(edge[1]).add(edge[0]);
        }
        int ans = 0;
        for(int key:sameVal.keySet()){
            Map<Integer, Integer> groupSize = new HashMap<>();
            for(int node:sameVal.get(key)){
                for(int next:graph.get(node)){
                    combine(node, next);
                }
            }
            for(int node:sameVal.get(key)){
                int fa = find(node);
                groupSize.put(fa, groupSize.getOrDefault(fa, 0)+1);
            }
            for(int val:groupSize.values()){
                ans += (val*(val+1))/2;
            }
        }
        return ans;
    }
    private int find(int a){
        if(fa[a]==a) return a;
        else return fa[a]=find(fa[a]);
    }
    private void combine(int a, int b){
        a = find(a);
        b = find(b);
        if(a==b) return;
        fa[b]=a;
    }
}