Number of Good Paths

Updated on 14 July, 2025
Number of Good Paths header image

Problem Statement

In this problem, we deal with a tree structure which is defined as a connected, undirected graph with no cycles. This tree consists of n nodes, each uniquely numbered from 0 to n - 1, with each node connected by exactly n - 1 edges. Each node of the tree holds a value, described by an array vals where the value of the i-th node is vals[i].

An edge is represented by a pair of nodes, given in the array edges, where each pair [ai, bi] denotes an undirected edge connecting the nodes ai and bi.

The task is to determine the number of "good paths" within this tree structure. A "good path" is defined by the following conditions:

  1. The path starts and ends at nodes that have identical values.
  2. Every node on the path, including the start and end, must have a value less than or equal to the value at the start/end nodes. Specifically, the value at the start (or end) node should be the maximum along the path.

The objective is to return the total distinct good paths in the tree. A key detail is that a path and its reverse are considered the same, and a single node is also counted as a valid path.

Examples

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 * 104
  • 0 <= vals[i] <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents a valid tree.

Approach and Intuition

Given the constraints and requirements of the problem, finding good paths requires checking potential paths emanating from each node, under the specific conditions of the problem. Our approach can be outlined as follows:

  1. Use Depth-First Search (DFS) to traverse the tree:

    • Start DFS from each node in the tree, initiating potential paths.
    • As we traverse, maintain the maximum value found on the current path. If a node's value exceeds this maximum, that path can't be extended further.
  2. Count paths:

    • For each node's DFS traversal, if we reach a node which matches the starting node's value, and if no node in between exceeds this value, increment our path count.
    • To avoid counting the same path multiple times (like a reverse of a path), we can consider a path counting method based on sorted node pairs or hashable structures.
  3. Handle the tree's connectivity:

    • Since each node is connected in exactly one way to the tree (except the root which has no parent), make sure not to backtrack to the parent node during DFS, which ensures every path is only considered once.
  4. Optimize:

    • Use memoization to store good paths found from each node to avoid redundant calculations.
    • Remember to account for every unique path once, so use a set or similar structure to ensure distinct paths are counted.

Given the size constraints (1 <= n <= 30000), the algorithm is designed to run efficiently in linear time concerning the number of nodes and edges, as each edge and node is essentially visited once.

Solutions

  • C++
cpp
class DisjointSet {
private:
    vector<int> leader, size;
    
public:
    DisjointSet(int cnt) {
        leader.resize(cnt);
        size.resize(cnt, 0);
        for (int id = 0; id < cnt; id++) {
            leader[id] = id;
        }
    }
    int find_leader(int x) {
        if (leader[x] != x) leader[x] = find_leader(leader[x]);
        return leader[x];
    }
    void merge(int x, int y) {
        int rootX = find_leader(x), rootY = find_leader(y);
        if (rootX == rootY) {
            return;
        } else if (size[rootX] < size[rootY]) {
            leader[rootX] = rootY;
        } else if (size[rootX] > size[rootY]) {
            leader[rootY] = rootX;
        } else {
            leader[rootY] = rootX;
            size[rootX]++;
        }
    }
};
    
class Solution {
public:
    int numberOfGoodPaths(vector<int>& values, vector<vector<int>>& links) {
        int nodeCount = values.size();
        vector<vector<int>> adjacency(nodeCount);
        for (auto& link : links) {
            adjacency[link[0]].push_back(link[1]);
            adjacency[link[1]].push_back(link[0]);
        }
        // Group nodes by values in ascending order.
        map<int, vector<int>> valueGroupMap;
        for (int node = 0; node < nodeCount; node++) {
            valueGroupMap[values[node]].push_back(node);
        }
    
        DisjointSet dsu(nodeCount);
        int pathCount = 0;
    
        // Process each group of nodes with the same value.
        for (auto& [val, nodes] : valueGroupMap) {
            // Link sets of the node with its neighbors that have equal or less value.
            for (int node : nodes) {
                for (int neighbor : adjacency[node]) {
                    if (values[node] >= values[neighbor]) {
                        dsu.merge(node, neighbor);
                    }
                }
            }
            // Count all nodes in the current sets to calculate number of paths.
            unordered_map<int, int> componentSize;
            for (int u : nodes) {
                int root = dsu.find_leader(u);
                componentSize[root]++;
            }
            // Calculate paths for each group of connected nodes.
            for (auto& [_, size] : componentSize) {
                pathCount += (size * (size + 1) / 2);
            }
        }
        return pathCount;
    }
};

The solution outlined solves the problem of calculating the "Number of Good Paths" using a C++ program employing a Disjoint Set Union (DSU) data structure for efficient connectivity checks among nodes. The solution breaks down into several key operations:

  1. Define the DisjointSet class to manage union and find operations. This includes methods to find the leader of a set, and to merge two sets together, adjusting leaders and sizes accordingly to maintain a balanced tree structure.

  2. Implement the main logic in the Solution class where the numberOfGoodPaths function computes the number of good paths. This function performs the following:

    • Initialize an adjacency list for each node based on the input links to represent the graph.
    • Group the nodes by their values using a map where the key is the node value, and the value is a list of nodes having that value. This aids in processing nodes with equal values together.
    • Iterate through each value group, merging nodes that are directly connected and have a value less than or equal to the current node's value using the Disjoint Set.
    • After forming groups (components) of connected nodes for each unique value, compute the possible good paths within each component using the combination formula ( n(n+1)/2 ) where ( n ) is the size of the component.

The beauty of this solution lies in its ability to efficiently manage connected components using the Disjoint Set while considering graph constraints based on node values. The result is an optimized calculation of paths satisfying specific value-based connectivity rules, ideal for scenarios with large graphs and diverse node values.

  • Java
java
class DisjointSet {
    int[] leader;
    int[] treeRank;
    
    public DisjointSet(int capacity) {
        leader = new int[capacity];
        for (int i = 0; i < capacity; i++)
            leader[i] = i;
        treeRank = new int[capacity];
    }
    
    public int findRoot(int x) {
        if (leader[x] != x)
            leader[x] = findRoot(leader[x]);
        return leader[x];
    }
    
    public void mergeSets(int x, int y) {
        int rootX = findRoot(x), rootY = findRoot(y);
        if (rootX == rootY) {
            return;
        } 
        if (treeRank[rootX] < treeRank[rootY]) {
            leader[rootX] = rootY;
        } else if (treeRank[rootX] > treeRank[rootY]) {
            leader[rootY] = rootX;
        } else {
            leader[rootY] = rootX;
            treeRank[rootX]++;
        }
    }
}
    
class Solution {
    public int numberOfGoodPaths(int[] vals, int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1];
            graph.computeIfAbsent(u, k -> new ArrayList<Integer>()).add(v);
            graph.computeIfAbsent(v, k -> new ArrayList<Integer>()).add(u);
        }
    
        int n = vals.length;
        TreeMap<Integer, List<Integer>> valueGroups = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            valueGroups.computeIfAbsent(vals[i], k -> new ArrayList<Integer>()).add(i);
        }
    
        DisjointSet dsu = new DisjointSet(n);
        int totalPaths = 0;
    
        for (int value : valueGroups.keySet()) {
            for (int node : valueGroups.get(value)) {
                if (!graph.containsKey(node))
                    continue;
                for (int neighbor : graph.get(node)) {
                    if (vals[node] >= vals[neighbor]) {
                        dsu.mergeSets(node, neighbor);
                    }
                }
            }
            Map<Integer, Integer> countInSet = new HashMap<>();
            for (int u : valueGroups.get(value)) {
                countInSet.put(dsu.findRoot(u), countInSet.getOrDefault(dsu.findRoot(u), 0) + 1);
            }
            for (int setSize : countInSet.values()) {
                totalPaths += setSize * (setSize + 1) / 2;
            }
        }
        return totalPaths;
    }
}

The provided Java solution involves determining the number of "good paths" among vertices in a graph based on certain conditions. The graph is represented via nodes and edges, where each node has a value, and edges connect pairs of nodes.

  • Data Structures Used:

    • DisjointSet Class: Implements union-find algorithm to manage sets of elements.
    • Map and ArrayList: Used to represent the graph and manage groups of nodes with the same values.
  • Main Steps in the Solution:

    1. Initializing Graph Structure:

      • Nodes are represented using a hash map where each node points to a list of its connected neighbors.
    2. Grouping Nodes Based on Values:

      • A TreeMap is utilized to group nodes by their values, ensuring the groups are processed in ascending order of values.
    3. Union-Find Application on Each Group:

      • For each group of nodes (starting with the lowest value), the algorithm tries to merge nodes into sets if they are directly connected by an edge and the starting node's value is not less than the neighboring nodes' values.
    4. Counting Good Paths:

      • After processing all connections, the number of elements in each set is used to determine the number of "good paths". This is calculated using the formula for combinations (n * (n + 1) / 2), which counts the possible paths (including the individual node path).
  • Output Determination:

    • The function returns the total number of good paths based on the dynamic application of the union-find operations guided by the graph structure and node values.

This solution efficiently combines union-find operations with value-based processing steps to explore possible combinations of paths that qualify as "good" according to the problem's conditions.

Comments

No comments yet.