2421. 好路徑的數目

思路

給定一些節點對應的數值，以及有哪些連接的邊，找出一共有多少個好路徑。
好路徑的定義是：從起點走到終點，起點終點的值相同，中途的路徑都比起點數值小。
問有幾條這樣的路徑，一條路徑和它的反向路徑視為相同的路徑。
單一個點也算做是合法路徑。

1. 在計算路徑時，如果中途有比自己大的數字存在，這條路徑就不是一個好路徑。
2. 因此排序連接的路徑，根據連接的數字大小去排序，先連接數值小的，再連接數值大的，方便後續計算。
3. 連接時，如果兩個集合 $a,b$ 的最大值相等，這兩個集合形成的好路徑個數就是 $na\times{nb}$ 。

• $na$ 是 $a$ 當中最大值的個數。
• $nb$ 是 $b$ 當中最大值的個數。

程式碼

並查集

class Solution {
private:
    static const int MX = 30001;
    int parent[MX]; // 最大值用來代表集合，紀錄的是編號
    int maxcnt[MX]; // 紀錄集合最大值的數量
    void build(int n) {
        iota(parent, parent + n, 0);
        fill(maxcnt, maxcnt + n, 1);
    }
    int find(int x) {
        if(x != parent[x]) {
            parent[x]  = find(parent[x]);
        }
        return parent[x];
    }
    int unite(int x, int y, vector<int>& vals) {
        // 將邊由小合併到大，中途計算好路徑的數量，
        int rootX = find(x);
        int rootY = find(y);
        int res = 0;
        if(vals[rootX] > vals[rootY]) { // 判斷兩集合最大值的大小
            parent[rootY] = rootX; 
        }
        else if(vals[rootX] < vals[rootY]) {
            parent[rootX] = rootY;
        }
        else { // vals[rootX] == vals[rootY]
            // 大小值相等，紀錄新增的好路徑數目。
            res = maxcnt[rootX] * maxcnt[rootY];
            parent[rootY] = rootX;
            maxcnt[rootX] += maxcnt[rootY];
        }
        return res;
    }
public:
    int numberOfGoodPaths(vector<int>& vals, vector<vector<int>>& edges) {
        int n = vals.size();
        build(n);
        // 將連接的邊，根據兩端點的數值，由小到大排序
        sort(edges.begin(), edges.end(), [&](vector<int>& a, vector<int>& b) {
            return max(vals[a[0]], vals[a[1]]) < max(vals[b[0]], vals[b[1]]);
        }); 
        int res = n; // 每一個獨立的點也是一個好路徑
        for(auto& e : edges) {
            res += unite(e[0], e[1], vals);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(E\log{E}+E)$，$E$ 是edges的大小。
• 空間複雜度：$O(n)$