<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>

###### tags: `Leetcode`

# 2421. Number of Good Paths

###### Link : https://leetcode.com/problems/number-of-good-paths/description/

## 題目
找到Good Path的數量
Good Path:起點和終點為相同數值且路徑中的數值小於等於起點或終點
## 程式碼 <a href="https://hackmd.io/s9CujEpmTpW0LNmoqL_klw"> Disjiont Set-Union find(DSU) </a>

class DSU{
public:
    DSU(int n) : parent(n){
        for(int i=0; i < n; i++){
            parent[i] = i;
        }
    }
    int findParent(int x){
        if(parent[x] == x)
            return x;
        return parent[x] = findParent(parent[x]);
    }
    void UNION(int x, int y){
        int parentx = findParent(x), parenty = findParent(y);
        if(parentx == parenty)
            return;
        parent[parenty] = parent[parentx];
        return;
    }
    vector<int> parent;
};
class Solution {
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size(), ans=0;
        vector<vector<int>> adj(n);
        for(auto &edge : edges){//adj list
            adj[edge[0]].push_back(edge[1]);
            adj[edge[1]].push_back(edge[0]);
        }
        DSU dsu(n);
        map<int, vector<int>> valToNode;//<數值,對應到是這個數值的點>
        for(int i=0; i<n; i++){
            valToNode[vals[i]].push_back(i);
        }
        for(auto [value, nodes] : valToNode){
            for(auto &node : nodes){
                for(auto &neighbor : adj[node]){
                    if(vals[neighbor] <= vals[node])//如果這個點的鄰居的數值小於這個點
                        dsu.UNION(node, neighbor);//將兩個點連接
                }
            }
            unordered_map<int, int> freqOfRoot;//計算加入的點有多少是在同一棵樹中
            for(auto &node : nodes){
                freqOfRoot[dsu.findParent(node)]++;
            }
            for(auto it : freqOfRoot){
                ans += it.second * (it.second + 1) / 2;//路徑數量等於每棵分開的樹所新增的點數量*(新增的點數量+1)/2
            }
        }
        return ans;
    }
};

今天一整天都在搞這個
我好快樂喔