2421.Number of Good Paths
===

###### tags: `Hard`,`Array`,`Tree`,`Graph`,`Union Find`

[2421. Number of Good Paths](https://leetcode.com/problems/number-of-good-paths/)

### 題目描述
There is a tree (i.e. a connected, undirected graph with no cycles) consisting of `n` nodes numbered from `0` to `n - 1` and exactly `n - 1` edges.

You are given a **0-indexed** integer array `vals` of length `n` where `vals[i]` denotes the value of the i^th^ node. You are also given a 2D integer array `edges` where `edges[i]` = [$a_i$, $b_i$] denotes that there exists an **undirected** edge connecting nodes $a_i$ and $b_i$.

A **good path** is a simple path that satisfies the following conditions:

The starting node and the ending node have the **same** value.

All nodes between the starting node and the ending node have values **less than or equal to** the starting node (i.e. the starting node's value should be the maximum value along the path).

Return *the number of distinct good paths.*

Note that a path and its reverse are counted as the **same** path. For example, `0 -> 1` is considered to be the same as `1 -> 0`. A single node is also considered as a valid path.

### 範例

**Example 1:**


Input: vals = [1,3,2,1,3], edges = [[0,1],[0,2],[2,3],[2,4]]
Output: 6
Explanation: There are 5 good paths consisting of a single node.
There is 1 additional good path: 1 -> 0 -> 2 -> 4.
(The reverse path 4 -> 2 -> 0 -> 1 is treated as the same as 1 -> 0 -> 2 -> 4.)
Note that 0 -> 2 -> 3 is not a good path because vals[2] > vals[0].

**Example 2:**


Input: vals = [1,1,2,2,3], edges = [[0,1],[1,2],[2,3],[2,4]]
Output: 7
Explanation: There are 5 good paths consisting of a single node.
There are 2 additional good paths: 0 -> 1 and 2 -> 3.

**Example 3:**


Input: vals = [1], edges = []
Output: 1
Explanation: The tree consists of only one node, so there is one good path.

**Constraints**:

* `n` == `vals.length`
* 1 <= `n` <= 3 * 10^4^
* 0 <= `vals[i]` <= 10^5^
* `edges.length` == `n` - 1
* `edges[i].length` == 2
* 0 <= $a_i$, $b_i$ < `n`
* $a_i$ != $b_i$
* `edges` represents a valid tree.

### 解答
#### C++
##### 思路:
1. 找path, 頭尾值需相同, path途中值小於等於頭尾
2. 如何找到及遍歷符合的path? 如何避免重複path?
3. 看答案
4. 從最小值的node開始做, 把出現過的node可以連接的當作一群, 每有新的node加入群時, 因為是從值小的部分開始做, 加入的node形成的path勢必合法, 故結果只需看新加入群的node有幾個即可算可組成多少path
##### 做法:
1. adjacent list 紀錄每個node與其相連值較小或等於的node
2. 建立map<int, vector<int>>代表某個值包含哪些node
3. 由小至大處理每一個值的nodes
4. 用Union find連接當前處理的nodes跟之前的nodes, 形成可能不只一個的component(可用編號小的當component head)
5. 遍歷nodes確認各別屬於哪每一個component, cnt表示每一個component出現有cnt個node是新加入的, 這些可以組成cnt*(cnt-1)/2個path + 每一個node單獨形成一個path共有cnt個
6. 重複3~6

class Solution {
public:
    class UnionFind{
        private:
            vector<int> id;
        public:
            UnionFind(int cnt){
                id = vector<int>(cnt);
                for(int i = 0; i < cnt; i++)
                    id[i] = i;
            }
            int find(int p){
                if(p == id[p]) return p;
                int root = find(id[p]);
                id[p] = root;
                return root;
            }
            void connect(int p, int q){
                int i = find(p), j = find(q);
                if(i == j) return;
                if(i > j)
                    id[i] = j;
                else
                    id[j] = i;
            }
    };
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size(), goodPaths = 0;
        vector<vector<int>> adj(n);
        map<int, vector<int>> sameValues;
        for(auto& e : edges){
            int u = e[0], v = e[1];
            if(vals[u] >= vals[v])
                adj[u].push_back(v);
            else if(vals[v] >= vals[u])
                adj[v].push_back(u);
        }
        for(int i = 0; i < n; i++)
            sameValues[vals[i]].push_back(i);
        UnionFind uf(n);
        for(auto &[value, allNodes] : sameValues){
            for(int u : allNodes){
                for(int v : adj[u]){
                    uf.connect(u, v);
                }
            }
            unordered_map<int, int> group;
            for(int u : allNodes)
                group[uf.find(u)]++;
            for(auto &[_, size] : group)
                goodPaths += (size * (size-1) / 2);
            goodPaths += allNodes.size();
        }
        return goodPaths;
    }
};

> [name=XD] [time= Jan 15, 2023]

Time: $O(n+m*log(m))$ `n`為node數, `m`為node中不同的值
Extra Space: $O(n)$

### Reference

[回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)