3108. Minimum Cost Walk in Weighted Graph

HardBit ManipulationUnion FindGraphArray

Problem Description

There is an undirected weighted graph with n vertices labeled from 0 to n - 1. You are given the integer n and an array edges, where edges[i] = [uᵢ, vᵢ, wᵢ] indicates that there is an edge between vertices uᵢ and vᵢ with a weight of wᵢ.

A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once.

The cost of a walk starting at node u and ending at node v is defined as the bitwise AND of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is w₀, w₁, w₂, ..., wₖ, then the cost is calculated as w₀ & w₁ & w₂ & ... & wₖ, where & denotes the bitwise AND operator.

You are also given a 2D array query, where query[i] = [sᵢ, tᵢ]. For each query, you need to find the minimum cost of the walk starting at vertex sᵢ and ending at vertex tᵢ. If there exists no such walk, return -1.

Return the array answer, where answer[i] denotes the minimum cost of a walk for query i.

Intuition

To solve the problem, consider the nature of the bitwise AND operation: a number becomes smaller or remains the same when ANDed with another number. Hence, to find the minimum cost, we should find the bitwise AND of all edge weights in the same connected component of the graph.

Connected Components Detection: Use a union-find structure (or disjoint-set union, DSU) to determine the connected components in the graph. Union-find helps us efficiently manage and identify which vertices belong to the same component.
Calculate AND for Components: Once the connected components are determined, traverse through each edge, find the root of its component, and compute the bitwise AND of all weights associated with that component. Store this value in an array g.
Query Processing: For each query (sᵢ, tᵢ), check:
- If sᵢ equals tᵢ, the walk cost is 0 since it's start and end at the same vertex.
- If sᵢ and tᵢ are in the same component, the result for this query is the AND value stored for that component.
- If they are not in the same component, return -1.

Using the union-find data structure ensures optimal performance in grouping vertices and retrieving component information, making it efficient to handle multiple queries.

Learn more about Union Find and Graph patterns.

Solution Approach

The solution to this problem is based on applying a Union-Find data structure to manage and calculate the minimum cost of walks between vertices of an undirected weighted graph. Here's how the solution is broken down:

Union-Find Initialization:
- A UnionFind class is implemented to manage the connected components of the graph. It includes methods for find (to determine the root component of a node) and union (to merge two nodes into one component).
Component Union:
- All edges are used to union their connected vertices. This operation groups all vertices into their respective connected components. Thus, for any two nodes u and v connected by an edge e = (u, v), the same root will be assigned.
Compute Bitwise AND for Components:
- After merging all nodes into components, traverse all edges again. For each one, find the connected component's root, and apply a bitwise AND operation to the weights of all edges within each component. Store this resulting 'minimum cost walk' for each component.
Query Execution:
- For each query (s, t), determine the following:
  - If s == t, the minimum cost walk is 0 because no edges are needed to walk from a node to itself.
  - If s and t belong to the same connected component, return the precomputed bitwise AND value for their component.
  - Otherwise, if they aren't in the same component, return -1, as no walk exists between these nodes.

By efficiently managing these operations, the approach is computationally efficient, leveraging the power of union-find to minimize walk costs evaluation across multiple queries. The complexity is primarily linear relative to the number of nodes and edges, plus the processing of each query.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider a small graph with n = 4 vertices and the following edges with weights:

Edge between vertex 0 and 1 with weight 3.
Edge between vertex 1 and 2 with weight 2.
Edge between vertex 2 and 3 with weight 4.

The edges array is represented as [[0, 1, 3], [1, 2, 2], [2, 3, 4]].

Suppose you have the following queries:

Query [0, 3]: Find the minimum cost of the walk from vertex 0 to vertex 3.
Query [1, 1]: Find the minimum cost of the walk from vertex 1 to vertex 1.
Query [0, 2]: Find the minimum cost of the walk from vertex 0 to vertex 2.

Let's walk through the solution approach using this example:

Union-Find Initialization:
- Initialize the union-find structure for n vertices.
Component Union:
- Process each edge to merge components:
  - Combine vertices 0 and 1 into one component using the edge [0, 1, 3].
  - Merge vertices 1 and 2 using the edge [1, 2, 2], linking 0, 1, and 2 into one component.
  - Connect vertices 2 and 3 with the edge [2, 3, 4], essentially combining all vertices into a single component.
Compute Bitwise AND for Components:
- Traverse the edges again to compute the bitwise AND of weights for each component:
  - For the single component (0, 1, 2, 3), calculate the AND of weights 3, 2, and 4 resulting in 3 & 2 & 4 = 0.
Query Execution:
- Query [0, 3]:
  - Both vertices 0 and 3 are in the same component. The minimum cost is the precomputed AND value for the component, i.e., 0.
- Query [1, 1]:
  - Since s equals t (both are 1), the minimum cost is 0 (no edges required).
- Query [0, 2]:
  - Vertices 0 and 2 are in the same component. The minimum cost is the precomputed value, i.e., 0.

The final answer array for the queries is [0, 0, 0].

Solution Implementation

1from typing import List
2
3class UnionFind:
4    def __init__(self, n: int):
5        # Initialize the parent list with each node as its own parent
6        self.parent = list(range(n))
7        # Initialize the size of each component to 1
8        self.size = [1] * n
9
10    def find(self, x: int) -> int:
11        # Path compression to find the root of x
12        if self.parent[x] != x:
13            self.parent[x] = self.find(self.parent[x])
14        return self.parent[x]
15
16    def union(self, a: int, b: int) -> bool:
17        # Find roots of a and b
18        root_a, root_b = self.find(a), self.find(b)
19        # If they are already in the same component, return False
20        if root_a == root_b:
21            return False
22        # Union by size: attach the smaller tree under the larger tree
23        if self.size[root_a] > self.size[root_b]:
24            self.parent[root_b] = root_a
25            self.size[root_a] += self.size[root_b]
26        else:
27            self.parent[root_a] = root_b
28            self.size[root_b] += self.size[root_a]
29        return True
30
31class Solution:
32    def minimumCost(self, n: int, edges: List[List[int]], queries: List[List[int]]) -> List[int]:
33        # Initialize the minimum weight array with -1
34        min_weights = [-1] * n
35        uf = UnionFind(n)
36      
37        # Perform unions for each edge
38        for u, v, _ in edges:
39            uf.union(u, v)
40      
41        # Determine the minimum weight for each connected component
42        for u, _, w in edges:
43            root = uf.find(u)
44            # Use bitwise AND to maintain the minimum weight
45            min_weights[root] &= w
46
47        def query_cost(u: int, v: int) -> int:
48            # If the query is within the same node, the cost is 0
49            if u == v:
50                return 0
51            # Check if u and v are in the same component
52            root_u, root_v = uf.find(u), uf.find(v)
53            # Return the minimum weight if connected, else -1
54            return min_weights[root_u] if root_u == root_v else -1
55
56        # Apply the query on all pairs
57        return [query_cost(s, t) for s, t in queries]
58

1import java.util.Arrays;
2
3// Union-Find data structure for dynamic connectivity
4class UnionFind {
5    private final int[] parent;  // Parent array for each element
6    private final int[] size;    // Size array to keep track of the size of each component
7
8    // Constructor to initialize the Union-Find structure with 'n' elements
9    public UnionFind(int n) {
10        parent = new int[n];
11        size = new int[n];
12        for (int i = 0; i < n; ++i) {
13            parent[i] = i;        // Each element is initially its own parent
14            size[i] = 1;          // Initial size of each component is 1
15        }
16    }
17
18    // Method to find the root of element 'x' with path compression
19    public int find(int x) {
20        if (parent[x] != x) {
21            parent[x] = find(parent[x]); // Recursively find and compress the path
22        }
23        return parent[x];
24    }
25
26    // Method to union two elements 'a' and 'b'
27    public boolean union(int a, int b) {
28        int rootA = find(a), rootB = find(b);
29        if (rootA == rootB) {
30            return false; // 'a' and 'b' are already connected
31        }
32        // Union by size: attach smaller tree under larger tree
33        if (size[rootA] > size[rootB]) {
34            parent[rootB] = rootA;
35            size[rootA] += size[rootB];
36        } else {
37            parent[rootA] = rootB;
38            size[rootB] += size[rootA];
39        }
40        return true;
41    }
42
43    // Method to get the size of the component containing element 'x'
44    public int size(int x) {
45        return size[find(x)];
46    }
47}
48
49// Solution class to solve the problem using UnionFind
50class Solution {
51    private UnionFind unionFind;
52    private int[] costGroup;
53
54    // Method to compute the minimum cost for each query
55    public int[] minimumCost(int n, int[][] edges, int[][] queries) {
56        unionFind = new UnionFind(n);
57        // Union all the connected nodes according to the edges
58        for (int[] edge : edges) {
59            unionFind.union(edge[0], edge[1]);
60        }
61        costGroup = new int[n];
62        Arrays.fill(costGroup, -1);
63
64        // Compute the minimum cost for each connected component
65        for (int[] edge : edges) {
66            int root = unionFind.find(edge[0]);
67            if (costGroup[root] == -1) {
68                costGroup[root] = edge[2];
69            } else {
70                costGroup[root] &= edge[2];
71            }
72        }
73
74        int queryCount = queries.length;
75        int[] result = new int[queryCount];
76      
77        // Calculate the results for each query
78        for (int i = 0; i < queryCount; ++i) {
79            int source = queries[i][0], target = queries[i][1];
80            result[i] = queryCost(source, target);
81        }
82        return result;
83    }
84
85    // Helper method to calculate the cost between two nodes 'u' and 'v'
86    private int queryCost(int u, int v) {
87        if (u == v) {
88            return 0; // Same node has zero cost
89        }
90        int rootU = unionFind.find(u), rootV = unionFind.find(v);
91        // If both nodes are connected, return the associated cost; otherwise, return -1
92        return rootU == rootV ? costGroup[rootU] : -1;
93    }
94}
95

1#include <vector>
2#include <numeric> // For std::iota
3
4using namespace std;
5
6// Union-Find or Disjoint Set data structure
7class UnionFind {
8public:
9    // Constructor initializes Union-Find data structure
10    UnionFind(int n) {
11        parents = vector<int>(n);
12        sizes = vector<int>(n, 1);
13        // Assign each node as its own parent (initially)
14        iota(parents.begin(), parents.end(), 0);
15    }
16
17    // Unite two sets, returns true if successful, false if already united
18    bool unite(int a, int b) {
19        int rootA = find(a), rootB = find(b);
20        if (rootA == rootB) {
21            return false; // They are already united
22        }
23        // Union by size heuristic
24        if (sizes[rootA] > sizes[rootB]) {
25            parents[rootB] = rootA;
26            sizes[rootA] += sizes[rootB];
27        } else {
28            parents[rootA] = rootB;
29            sizes[rootB] += sizes[rootA];
30        }
31        return true;
32    }
33
34    // Find the root of the set containing x
35    int find(int x) {
36        if (parents[x] != x) {
37            // Path compression heuristic
38            parents[x] = find(parents[x]);
39        }
40        return parents[x];
41    }
42
43    // Get the size of the set containing x
44    int getSize(int x) {
45        return sizes[find(x)];
46    }
47
48private:
49    vector<int> parents, sizes; // Parents and sizes of each set
50};
51
52// Solution class for the problem
53class Solution {
54public:
55    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
56        costsForRoots = vector<int>(n, -1);
57        unionFind = new UnionFind(n);
58      
59        // Unite all edges in the union-find
60        for (auto& edge : edges) {
61            unionFind->unite(edge[0], edge[1]);
62        }
63
64        // Compute the minimum cost for the connected component starting at root
65        for (auto& edge : edges) {
66            int root = unionFind->find(edge[0]);
67            costsForRoots[root] &= edge[2];
68        }
69
70        vector<int> result;
71      
72        // Execute each query
73        for (auto& q : query) {
74            result.push_back(f(q[0], q[1]));
75        }
76      
77        return result;
78    }
79
80private:
81    UnionFind* unionFind; // Union-Find structure
82    vector<int> costsForRoots; // Minimum cost for each root of the connected component
83
84    // Helper method to determine the minimum cost between two nodes
85    int f(int u, int v) {
86        if (u == v) {
87            return 0; // Cost to itself is zero
88        }
89        int rootU = unionFind->find(u), rootV = unionFind->find(v);
90        return rootU == rootV ? costsForRoots[rootU] : -1; // -1 if they are not connected
91    }
92};
93

1// Union-Find data structure for maintaining disjoint sets with path compression and union by size
2let p: number[]; // Array to track the parent of each node
3let size: number[]; // Array to track the size of each component
4
5// Initialize the Union-Find structure
6function initializeUnionFind(n: number): void {
7    p = Array(n).fill(0).map((_, i) => i);
8    size = Array(n).fill(1);
9}
10
11// Find the root of the component for a given node with path compression
12function find(x: number): number {
13    if (p[x] !== x) {
14        p[x] = find(p[x]); // Path compression
15    }
16    return p[x];
17}
18
19// Union two components by size
20function union(a: number, b: number): boolean {
21    const pa = find(a);
22    const pb = find(b);
23    if (pa === pb) return false; // Already in the same component
24    if (size[pa] > size[pb]) {
25        p[pb] = pa;
26        size[pa] += size[pb];
27    } else {
28        p[pa] = pb;
29        size[pb] += size[pa];
30    }
31    return true;
32}
33
34// Get the size of the component containing a given node
35function getSize(x: number): number {
36    return size[find(x)];
37}
38
39// Function to determine the minimum cost for each query
40function minimumCost(n: number, edges: number[][], query: number[][]): number[] {
41    initializeUnionFind(n); // Initialize Union-Find for n nodes
42    const g: number[] = Array(n).fill(-1); // Array to store minimum cost for each component
43
44    // Union all edges
45    for (const [u, v, _] of edges) {
46        union(u, v);
47    }
48
49    // Calculate the minimum cost for each connected component
50    for (const [u, _, w] of edges) {
51        const root = find(u);
52        g[root] &= w; // Bitwise AND to find the minimum cost
53    }
54
55    // Helper function to answer the cost query between two nodes
56    const f = (u: number, v: number): number => {
57        if (u === v) return 0; // Same node, cost is zero
58        const [a, b] = [find(u), find(v)];
59        return a === b ? g[a] : -1; // Return the minimum cost if in the same component, else -1
60    };
61
62    // Map each query to its result using the helper function
63    return query.map(([u, v]) => f(u, v));
64}
65

Time and Space Complexity

The time complexity of the code is O((n + m + q) * α(n)). The code involves initializing the Union-Find structure, which takes O(n) time. The union operations for all edges take O(m * α(n)) time, where α(n) is the inverse Ackermann function, due to path compression and union by size optimizations. Each query uses find, which also takes O(q * α(n)) time. Together, this results in the overall time complexity of O((n + m + q) * α(n)).

The space complexity is O(n), because the Union-Find structure maintains two lists of size n: one for parent tracking and one for sizes. Additional space is used for the integer array g, also of size n, resulting in an overall space complexity of O(n).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know