Problem

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] = [ui, vi, wi] indicates that there is an edge between vertices ui and vi with a weight of wi.

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 w0, w1, w2, ..., wk, then the cost is calculated as w0 & w1 & w2 & ... & wk, where & denotes the bitwise AND operator.

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

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

Examples

Example 1:

graph TD
    A((0)) ---|7| B((1))
    B((1)) ---|7| D((3))
    B((1)) ---|1| C((2))
    E((4))
  
1
2
3
4
5

Input: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]
Output: [1,-1]
Explanation:
To achieve the cost of 1 in the first query, we need to move on the following edges: `0->1` (weight 7), `1->2` (weight 1), `2->1` (weight 1), `1->3` (weight 7).
In the second query, there is no walk between nodes 3 and 4, so the answer is -1.

Example 2:

graph TD
	A((0))
	B((1))
	C((2))
	
    A ---|15| B
    B ---|6| C
    B ---|1| C
    A ---|7| C
  
1
2
3
4

Input: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]
Output: [0]
Explanation:
To achieve the cost of 0 in the first query, we need to move on the following edges: `1->2` (weight 1), `2->1` (weight 6), `1->2` (weight 1).

Constraints:

  • 2 <= n <= 10^5
  • 0 <= edges.length <= 10^5
  • edges[i].length == 3
  • 0 <= ui, vi <= n - 1
  • ui != vi
  • 0 <= wi <= 10^5
  • 1 <= query.length <= 10^5
  • query[i].length == 2
  • 0 <= si, ti <= n - 1
  • si != ti

Solution

Method 1 - Using Union Find

To calculate the cost of a path in the graph, we use bitwise AND operations across edge weights and can reuse the same edges multiple times. Performing bitwise AND on edge weights reduces or preserves costs, making it optimal to utilise edges maximally to minimise path costs. Vertices that are reachable via connected edges form groups. Within each group, any path between two nodes has the same cost, as traversing all edges in the group ensures the minimum cost, which is derived from the AND operation on all connecting edges within that group.

Approach

Union-Find is applied on the edges to group connected vertices. During the union operation, a weights array tracks the weight of each connected group. When merging two groups, the group’s weight is updated by performing a bitwise AND operation between the existing weights of the groups and the weight of the edge connecting them. This ensures that the group’s weight reflects all edges used to merge vertices. Initially, weights are set to 131071 (binary 11111111111111111) as it exceeds 10^5.

For queries:

  • If si and ti are the same, return 0.
  • If si and ti are in separate groups, return -1.
  • If si and ti belong to the same group, return the group’s weight, representing the AND operation of all connected edges within the group.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    public static class UnionFind {
        int[] parent, rank, weights;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            weights = new int[n];
            Arrays.fill(weights, 131071);
            for (int i = 0; i < n; i++)
                parent[i] = i;
        }

        public int find(int x) {
            if (x != parent[x])
                parent[x] = find(parent[x]);
            return parent[x];
        }

        public void union(int x, int y, int weight) {
            int px = find(x);
            int py = find(y);
            if (rank[px] < rank[py])
                parent[px] = py;
            else
                parent[py] = px;
            weights[px] = weights[py] = weights[px] & weights[py] & weight;
            if (rank[px] == rank[py])
                rank[px]++;
        }

        public int minimumCostOfWalk(int x, int y) {
            if (x == y)
                return 0;
            if (find(x) != find(y))
                return -1;
            return weights[find(x)];
        }
    }

    public int[] minimumCost(int n, int[][] edges, int[][] query) {
        UnionFind uf = new UnionFind(n);
        for (int[] edge : edges)
            uf.union(edge[0], edge[1], edge[2]);
        int[] result = new int[query.length];
        for (int i = 0; i < query.length; i++)
            result[i] = uf.minimumCostOfWalk(query[i][0], query[i][1]);
        return result;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))  # Initially, each node is its own parent
        self.rank = [0] * n           # Rank is initially 0 for all nodes
        self.weights = [131071] * n   # Initialize weights to 131071 (binary: all 1s in 17 bits)

    def find(self, x: int) -> int:
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])  # Path compression for efficiency
        return self.parent[x]

    def union(self, x: int, y: int, weight: int) -> None:
        px = self.find(x)
        py = self.find(y)
        if px != py:
            # Union by rank to maintain balanced tree
            if self.rank[px] < self.rank[py]:
                self.parent[px] = py
            elif self.rank[px] > self.rank[py]:
                self.parent[py] = px
            else:
                self.parent[py] = px
                self.rank[px] += 1
            
            # Update weights using bitwise AND
            self.weights[px] = self.weights[py] = self.weights[px] & self.weights[py] & weight

    def minimum_cost_of_walk(self, x: int, y: int) -> int:
        if x == y:
            return 0  # The cost of walking to the same node is 0
        if self.find(x) != self.find(y):
            return -1  # If the nodes are in different groups, return -1
        return self.weights[self.find(x)]  # Return the minimum cost for the connected group


class Solution:
    def minimumCost(self, n: int, edges: List[List[int]], query: List[List[int]]) -> List[int]:
        uf = UnionFind(n)  # Initialize UnionFind for `n` nodes
        
        # Perform union operation for each edge
        for u, v, w in edges:
            uf.union(u, v, w)
        
        # Resolve each query
        return [uf.minimum_cost_of_walk(s, t) for s, t in query]

Complexity

  • ⏰ Time complexity: O(n), as Union-Find with path compression and rank operates close to O(n).
  • 🧺 Space complexity: O(n), as the Union-Find class uses additional arrays (parent, rank, and weights) with linear space requirements.