1724. Checking Existence of Edge Length Limited Paths II

Problem Description

The problem presents an undirected graph consisting of n nodes. An edge list describes the graph, with each element in the list representing an edge; an edge is defined by the nodes it connects and the distance between them. The edge list includes triples of the form [u_i, v_i, dis_i], indicating that there is an edge between nodes u_i and v_i having a distance dis_i. Note that this graph can have multiple edges between the same nodes and it might not be entirely connected.

The task is to implement a class DistanceLimitedPathsExist that is capable of handling two types of operations:

1. Initialization of the class with the undirected graph described by the edge list.
2. Handling queries to check if there is a path between a pair of nodes (p, q) such that every edge on that path has a distance strictly less than a given limit.

This is not just a problem of checking if a path exists, but it also involves ensuring that the distances of all edges along possible paths meet a specific condition (strictly less than the given limit).

Intuition

The intuitive approach to this problem is to find a way to efficiently check whether there is a feasible path between any two nodes, obeying the distance limit for each edge. A standard approach for checking connectivity in a graph is to use a Union-Find data structure, which can quickly determine if two nodes are in the same connected component. The challenge here is the limit constraint on the edge distance, which Union-Find doesn't handle in its basic form.

The provided solution uses a variant called Persistent Union-Find, which is an extension of the regular Union-Find DS. It can keep track of the component structure of the graph over time, which means we can query past states of the graph - this is perfect for our case because we need to consider edges by their distances.

Here's how we leverage the Persistent Union-Find:

1. Sort the edges in non-decreasing order of distance. This allows us to process connections progressively, starting from the smallest distance up.
2. Iterate through the sorted edges and perform unions in the data structure, effectively building up connectivity as the edge distances increase.
3. For each union operation, store the distance value at which this union occurred (the current distance acts as a timestamp). This enables us to know the point in time (in terms of edge distance) when two nodes became connected.

When we receive a query (p, q, limit), we can use the timestamped connectivity information to determine if p and q were connected before the given limit. We do this by checking if their ancestors in the data structure were united at a distance strictly less than limit. If they share a common ancestor at that state, it means that a path exists that satisfies the distance constraint.

The Persistent Union-Find is not a part of standard data structures but is an ingenious variation to suit the specific need of this problem, which is to respect the progressive nature of edge distances and to query past states based on these distances.

Learn more about Union Find, Graph and Minimum Spanning Tree patterns.

Solution Approach

The implementation of the solution involves the use of a specialized data structure: the Persistent Union-Find. Let's take a closer look at how this structure is implemented and its role in the solution:

1. Persistent Union-Find Structure: As an extension of the classic Union-Find, it introduces the concept of versions to keep track of the union operations over time. Each element in the Union-Find has a version which can be thought of as the timestamp (in this case, the distance) when the last union involving this element occurred.

   • self.rank is an array where each element represents the rank of the node. The rank is a heuristic used to keep the tree balanced in a classic Union-Find. It roughly represents the maximum height of the node in the tree.
   • self.p is a list representing the parent of each node. Initially, each node is its own parent, indicating that they are separate components.
   • self.version is a list with the same length as self.p, initialized to inf, which holds the timestamp of the last update for each node.

2. The find Method: The find method is used to find the root of the component to which a given node belongs. However, in the Persistent Union-Find, this method is extended to include time travel. It accepts an optional parameter t, which represents the time at which we want to query the component structure. The method will return the root of the component that the node belonged to at time t.

3. The union Method: This method links the components that include nodes a and b and also records the time t (the distance in this problem) at which the union occurred. It ensures that the root with the larger rank remains the root, while the one with the smaller rank gets connected below it. The version of the node that gets attached is updated to reflect the timestamp of the union.

4. Initialization (__init__): In the initialization of the DistanceLimitedPathsExist class, the Persistent Union-Find structure is created, and then the edge list is sorted by edge distances in non-decreasing order. The class iterates through the sorted edge list and uses the union method to build up the connectivity structure of the graph, with the distance of the currently processed edge as the timestamp. This builds a history of component connectivity in the data structure that can be queried later.

5. Querying (query): The query method checks if there exists a path between nodes p and q with edges less than limit. It uses the find method of the Persistent Union-Find with limit as the timestamp to find the components of p and q at a time just before the limit. If both nodes have the same root at that time, it indicates that there was a path between them with edge lengths strictly less than limit, and true is returned. Otherwise, false is returned.

By applying this algorithm, the code maximizes efficiency both in building the connectivity structure and answering the distance-limited path queries. The sort operation allows for progressive building of the graph’s connectivity structure, and the Persistent Union-Find enables quick union and find operations, which are especially suitable for the problem as it needs to consider only a subset of the edges based on their distances when answering queries.

Example Walkthrough

Let's illustrate the solution approach with an example. Suppose we have the following edges in an undirected graph:

1Edges: [ [1, 2, 4], [1, 3, 3], [2, 3, 2], [3, 4, 2] ]

1. First, we initialize the DistanceLimitedPathsExist class with our list of edges. The first task in our class constructor is to sort the edges:

1Sort by distance: [ [2, 3, 2], [3, 4, 2], [1, 3, 3], [1, 2, 4] ]

2. We then create our Persistent Union-Find structure:

1Initially, each node is its own parent:
2self.p = [1, 2, 3, 4]   // Node indices are adjusted to be 1-based.
3self.rank = [0, 0, 0, 0]
4self.version = [inf, inf, inf, inf]

3. Now, let's iterate through the sorted edge list and perform union operations while recording the distance as their version/timestamp.

4. Union edge [2, 3, 2]:

1self.union(2, 3, 2):
2self.p = [1, 2, 2, 4]
3self.version = [inf, 2, inf, inf]

Both node 2 and node 3's root is now node 2, as they are connected.

5. Union edge [3, 4, 2]:

1self.union(3, 4, 2):
2self.p = [1, 2, 2, 2]
3self.version = [inf, 2, inf, 2]

Node 4 also joins the component, now all three nodes (2, 3, and 4) have a common root, node 2.

6. Union edge [1, 3, 3]:

1self.union(1, 3, 3):
2self.p = [2, 2, 2, 2]
3self.version = [3, 2, inf, 2]

Node 1 is connected to the rest through node 3, which in turn is connected to node 2, so the root for all is now node 2.

7. Union edge [1, 2, 4]: This edge will not change the connectivity since these nodes are already connected; however, the version would be updated if the rank allowed it.

The final structure of the Persistent Union-Find after the unions looks like this:

1self.p = [2, 2, 2, 2]
2self.rank = [1, 0, 0, 0]  // The rank of node 1 increased as it became the root after the last union.
3self.version = [3, 2, inf, 2]

8. Now let's handle some queries. For example query(1, 4, 3):

The method first checks the roots of nodes 1 and 4 right before the limit of 3.

1self.find(1, 2) returns 2 (since at a distance of less than 3, the root of node 1 is 2)
2self.find(4, 2) returns 2 (since at a distance of less than 3, the root of node 4 is 2)

Since both nodes have the same root (node 2) at a distance less than 3, there is a path between node 1 and node 4 where every edge is strictly less than the limit, and the method returns true.

9. If a query asks something like query(1, 3, 2):

1self.find(1, 1) returns 1 (at a distance less than 2, node 1 is disconnected, its own parent)
2self.find(3, 1) returns 2 (at a distance less than 2, the root of node 3 is 2)

Node 1 and node 3 have different roots at a distance less than 2, indicating there isn't a path conforming to the limit. Hence the method would return false.

Through this example, it is evident how the Persistent Union-Find structure, with its versioning capability, allows us to efficiently check the existence of a path under a distance constraint between any two nodes.

Python Solution

1from typing import List
2
3class PersistentUnionFind:
4    def __init__(self, node_count):
5        # Initialize rank and parent pointers. Rank is initially 0 for all nodes.
6        # Parent pointer is initially pointing to the node itself (self loop).
7        # Version will track the time stamp at which the parent pointer changes.
8        self.rank = [0] * node_count
9        self.parent = list(range(node_count))
10        self.version = [float('inf')] * node_count
11
12    def find(self, node, timestamp=float('inf')):
13        # Recursively find the representative (root) of the set that node belongs to.
14        # version is checked to ensure that we use the correct version of parent.
15        if self.parent[node] == node or self.version[node] >= timestamp:
16            return node
17        return self.find(self.parent[node], timestamp)
18
19    def union(self, node1, node2, timestamp):
20        # Union by rank heuristic, also records the time of the merge for persistence.
21        parent1, parent2 = self.find(node1), self.find(node2)
22        # If both nodes have same parent, they are already in the same set.
23        if parent1 == parent2:
24            return False
25        # Attach the tree with less rank to the one with more rank.
26        if self.rank[parent1] > self.rank[parent2]:
27            self.version[parent2] = timestamp
28            self.parent[parent2] = parent1
29        else:
30            self.version[parent1] = timestamp
31            self.parent[parent1] = parent2
32            # If ranks are equal, increment the rank of the resulting tree.
33            if self.rank[parent1] == self.rank[parent2]:
34                self.rank[parent2] += 1
35        return True
36
37
38class DistanceLimitedPathsExist:
39    def __init__(self, node_count: int, edge_list: List[List[int]]):
40        # PersistentUnionFind instance to record changes over time.
41        self.puf = PersistentUnionFind(node_count)
42        # Sorting edges based on their distances to process in increasing order.
43        edge_list.sort(key=lambda x: x[2])
44        # Union sets with edges, prioritized by smallest distance.
45        for u, v, distance in edge_list:
46            self.puf.union(u, v, distance)
47
48    def query(self, node1: int, node2: int, limit: int) -> bool:
49        # Returns True if there is a path between node1 and node2 with distance less than 'limit'.
50        # This check is possible via the union-find data structure at the state just before 'limit'.
51        return self.puf.find(node1, limit) == self.puf.find(node2, limit)
52

Java Solution

1import java.util.Arrays; // Import Arrays class for sorting edges
2
3// PersistentUnionFind class implementing the Persistent Union-Find data structure
4class PersistentUnionFind {
5    private static final int INF = 1 << 30; // An upper bound constant representing infinity
6    private int[] rank; // Array representing the rank of each element
7    private int[] parent; // Array storing the parent for each element (representative of the set)
8    private int[] version; // Array storing the version at which the parent pointer was updated
9
10    // Constructor initializing the union-find structure for `n` elements
11    public PersistentUnionFind(int n) {
12        rank = new int[n];
13        parent = new int[n];
14        version = new int[n];
15      
16        // Initially, each element is its own parent (leader), with rank 0 and a version set to INF
17        for (int i = 0; i < n; i++) {
18            parent[i] = i;
19            version[i] = INF;
20        }
21    }
22
23    // Method to find the representative of an element `x` at time `t`
24    public int find(int x, int t) {
25        // Return the element itself if it is its own parent or if the version is after time `t`
26        if (parent[x] == x || version[x] >= t) {
27            return x;
28        }
29        // Recursively find the representative of the parent at time `t`
30        return find(parent[x], t);
31    }
32
33    // Method to perform union of two sets containing elements `a` and `b` at time `t`
34    public boolean union(int a, int b, int t) {
35        // Find the current representatives (leaders) for `a` and `b`
36        int pa = find(a, INF);
37        int pb = find(b, INF);
38
39        // If the representatives are the same, the elements are already in the same set
40        if (pa == pb) {
41            return false;
42        }
43
44        // Attach the tree with the lower rank to the one with the higher rank
45        if (rank[pa] > rank[pb]) {
46            version[pb] = t;
47            parent[pb] = pa;
48        } else {
49            version[pa] = t;
50            parent[pa] = pb;
51
52            // If the ranks are equal, increment the rank of the resulting set
53            if (rank[pa] == rank[pb]) {
54                rank[pb]++;
55            }
56        }
57        return true;
58    }
59}
60
61// Class to handle queries for checking if a path exists between two nodes with a distance limit
62class DistanceLimitedPathsExist {
63    private PersistentUnionFind puf; // Instance of PersistentUnionFind
64  
65    // Constructor that initializes the union-find structure and processes the edges
66    public DistanceLimitedPathsExist(int n, int[][] edgeList) {
67        puf = new PersistentUnionFind(n);
68        // Sort the edges by their weight (distance)
69        Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));
70      
71        // Perform the unions in the order of increasing edge weight
72        for (int[] edge : edgeList) {
73            puf.union(edge[0], edge[1], edge[2]);
74        }
75    }
76
77    // Method to query if a path exists between `p` and `q` with a distance less than `limit`
78    public boolean query(int p, int q, int limit) {
79        // Return true if the representatives of `p` and `q` are the same at a version just before `limit`
80        return puf.find(p, limit) == puf.find(q, limit);
81    }
82}
83

C++ Solution

1#include <vector>
2#include <climits>
3#include <algorithm>
4
5using std::vector;
6using std::sort;
7
8class PersistentUnionFind {
9private:
10    vector<int> rank_;
11    vector<int> parent_;
12    vector<int> version_;
13
14public:
15    // Constructor initializes the PersistentUnionFind with `n` elements.
16    PersistentUnionFind(int n) : rank_(n, 0), parent_(n), version_(n, INT_MAX) {
17        for (int i = 0; i < n; ++i) {
18            parent_[i] = i; // Each node is initially its own parent (self root).
19        }
20    }
21
22    // Finds the representative of the set that `x` is a member of.
23    // `t` is the timestamp or version before which we are finding the representative.
24    int find(int x, int t) {
25        // Path compression stops when we find the original parent,
26        // or the version of the current node is greater or equal to `t`.
27        if (parent_[x] == x || version_[x] >= t) {
28            return x;
29        }
30        return find(parent_[x], t); // Recursively find the representative.
31    }
32
33    // Unions the sets that contain `a` and `b`.
34    // `t` is the time/version at which this union operation happens.
35    bool unionSet(int a, int b, int t) {
36        int parentA = find(a, INT_MAX);
37        int parentB = find(b, INT_MAX);
38      
39        // No need to union if they are already in the same set.
40        if (parentA == parentB) {
41            return false;
42        }
43      
44        // Union by rank heuristic.
45        if (rank_[parentA] > rank_[parentB]) {
46            version_[parentB] = t; // Update version of the newly added node.
47            parent_[parentB] = parentA;
48        } else {
49            version_[parentA] = t; // Update version of the newly added node.
50            parent_[parentA] = parentB;
51            if (rank_[parentA] == rank_[parentB]) {
52                rank_[parentB]++; // Increment rank if they were same.
53            }
54        }
55        return true;
56    }
57};
58
59class DistanceLimitedPathsExist {
60private:
61    PersistentUnionFind puf_;
62
63public:
64    // Constructor creates an instance with `n` nodes, and processes the `edgeList`.
65    DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList) : puf_(n) {
66        // Sort the edge list based on the weight (distance) of the edges.
67        sort(edgeList.begin(), edgeList.end(),
68            [](const vector<int>& a, const vector<int>& b) {
69                return a[2] < b[2]; // Sorting in ascending order of edge weight.
70            });
71
72        // Union sets based on the sorted edges, with the weight as the timestamp.
73        for (const auto& edge : edgeList) {
74            puf_.unionSet(edge[0], edge[1], edge[2]);
75        }
76    }
77
78    // Queries if there is a path between node `p` and `q` with all edges less than `limit`.
79    bool query(int p, int q, int limit) {
80        // If `p` and `q` have the same representative before the `limit`,
81        // then there exists a path with all edges having distances less than `limit`.
82        return puf_.find(p, limit) == puf_.find(q, limit);
83    }
84};
85
86/**
87 * How to use the above classes:
88 * 
89 * // Create an object with 'n' nodes and a list of edges.
90 * DistanceLimitedPathsExist* obj = new DistanceLimitedPathsExist(n, edgeList);
91 * 
92 * // Query if a path exists between nodes 'p' and 'q' with a distance limit.
93 * bool hasPath = obj->query(p, q, limit);
94 *
95 * // If not needed anymore, don't forget to delete the created object to avoid memory leaks.
96 * delete obj;
97 */
98

Typescript Solution

1// Number of elements in the union-find structure.
2let rank: number[];
3// Parent array to represent the forest in the union-find structure.
4let parent: number[];
5// Version array to keep track of when each vertex was last updated.
6let version: number[];
7
8// Function to initialize the union-find structure with `n` elements.
9function initializeUnionFind(n: number): void {
10    rank = Array(n).fill(0);
11    parent = Array.from({ length: n }, (_, i) => i);
12    version = Array(n).fill(Infinity);
13}
14
15// Function to find the root of an element `x` with temporal limitation `t`.
16function find(x: number, t: number): number {
17    if (parent[x] === x || version[x] >= t) {
18        return x;
19    }
20    return find(parent[x], t);
21}
22
23// Function to merge the sets containing elements `a` and `b` at time `t`.
24function union(a: number, b: number, t: number): boolean {
25    const rootA = find(a, Infinity);
26    const rootB = find(b, Infinity);
27
28    // Return false if `a` and `b` are already in the same set.
29    if (rootA === rootB) {
30        return false;
31    }
32
33    // Merge the roots, considering their ranks, and update versions.
34    if (rank[rootA] > rank[rootB]) {
35        version[rootB] = t;
36        parent[rootB] = rootA;
37    } else {
38        version[rootA] = t;
39        parent[rootA] = rootB;
40        if (rank[rootA] === rank[rootB]) {
41            rank[rootB]++;
42        }
43    }
44
45    return true;
46}
47
48// Sorting edge list based on the edge distance.
49function initializeEdgeList(edgeList: number[][]): void {
50    edgeList.sort((a, b) => a[2] - b[2]);
51    for (const [u, v, dis] of edgeList) {
52        union(u, v, dis);
53    }
54}
55
56// Function to check if there is a path between `p` and `q` with a distance limit.
57function query(p: number, q: number, limit: number): boolean {
58    return find(p, limit) === find(q, limit);
59}
60
61// Some examples on how to use the global variables and functions.
62// Initialization could be done as follows:
63// initializeUnionFind(n);
64// initializeEdgeList(edgeList);
65
66// Doing a query can be executed like this:
67// const result = query(p, q, limit);
68

Time and Space Complexity

Time Complexity

The time complexity of the PersistentUnionFind class operations are as follows:

• init: Initializing the PersistentUnionFind with n elements has a time complexity of O(n) since it involves creating a list of size n for rank, initializing the array p with size n, and setting the version list with size n to infinity.

• find: The find operation is a recursive function that, in the worst-case scenario (without path compression), could traverse the entire height of the tree, leading to a time complexity of O(h) where h is the height of the tree.

• union: The union operation involves two find operations and then, depending on the rank, potentially updating a parent pointer and rank. In the worst-case scenario, these operations have a time complexity of O(h) where h is the height of the tree. However, since the rank is used to ensure that the smaller tree is merged into the larger one, the height of the tree is limited to O(log n) where n is the number of elements.

• For the DistanceLimitedPathsExist class:

  • init: Sorting the edge list takes O(E log E) time, where E is the number of edges. The subsequent union operations of all edges take O(E log n) time. Therefore, the overall time complexity for the initialization is O(E log E + E log n). Since the E log E term dominates, we can say the initialization time complexity is O(E log E).

  • query: The query operation involves two find operations, each having a time complexity of O(log n), thus the total time complexity of a query is O(log n).

Space Complexity

The space complexity of the PersistentUnionFind class is O(n) since it maintains three lists (rank, p, and version) each of size n.

The space complexity of the DistanceLimitedPathsExist class is also O(n) for storing the PersistentUnionFind instance. However, the edge list provided as input is only used during initialization and is not stored, thus not contributing to the space complexity beyond the initial setup.

Therefore, the overall space complexity of the system (combining PersistentUnionFind and DistanceLimitedPathsExist) is O(n).

Learn more about how to find time and space complexity quickly.