2421.Number of Good Paths

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

2421. 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⁴
• 0 <= vals[i] <= 10⁵
• 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;
    }
};

XD Jan 15, 2023

Time:

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

$O(n)$

Reference

回到題目列表