Reachable nodes in the new graph

Moderate
0/80
Average time to solve is 20m
4 upvotes
Asked in companies
AmazonMorgan StanleySYSVINE

Problem statement

You are given an undirected graph with ‘n’ nodes labeled from ‘0’ to ‘n - 1’. The graph is given in as an array of ‘edges’, where ‘edges[i] = [u, v, sz]’ means there is an edge between node ‘u’ and ‘v’ in the given graph. Create a new graph by replacing the edge between ‘u’ and ‘v’ with a chain of size ‘sz’.

To create a chain of size ‘sz’ between nodes ‘(u, v)’, create ‘sz’ new nodes and ‘sz + 1’ new edges. The new nodes are ‘X1, X2, … , Xsz’ and the new edges are ‘(u, X1), (X1, X2), (X2, X3), … , (X(sz-1), Xsz), (Xsz, v)’.

A node is reachable from node ‘0’ if it’s at a distance of less than or equal to ‘m’ edges. Your task is to find the number of nodes reachable from node ‘0’ in the new graph.

Example: 
‘n = 3’, ‘m = 4’
‘edges = [ [0, 2, 8], [0, 1, 1], [1, 2, 0] ]’

example

The reachable nodes are highlighted in red color. So, the answer is ‘9’. Node ‘0’, itself included in the answer.
Note: 
1. For an edge ‘[u, v, sz]’, if ‘sz = 0’, then there is no chain, and ‘(u, v)’ is an edge in the new graph.

2. The graph doesn’t contain parallel edges or self-loops.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

The first line of each test case contains three integers ‘n’, ‘m’, and ‘numOfPairs’, denoting the number of nodes in the graph, the maximum allowed distance from node ‘0’, and the size of the ‘edges’ array. Then, ‘numOfPairs’ lines follow.

Each line contains three integers representing an element in ‘edges’.
Output format: 
For every test case, print a single line containing a single integer denoting the number of nodes reachable from node ‘0’ in the new graph.

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= n <= 500  
0 <= m <= 10 ^ 9
0 <= numOfPairs <= min(n * (n - 1) / 2, 10^3)
0 <= edges[i].u < edges[i].v < n
0 <= edges[i].sz <= 10^5
Each element of ‘edges’ contains exactly three integers.

Where ‘T’ is the number of test cases, ‘n’ is the number of nodes, ‘m’ is the maximum allowed distance from node ‘0’, and ‘numOfPairs’ is the size of the array ‘edges’.

Time limit: 1 second

Sample input 1:

2
4 3 5
0 1 4
1 3 0
0 3 1
0 2 1
2 3 4
3 7 2
0 1 5
1 2 3

Sample output 1:

11
8

Explanation of sample input 1:

Test Case 1:
‘n = 4’, ‘m = 3’
‘edges = [ [0, 1, 4], [1, 3, 0], [0, 3, 1], [0, 2, 1], [2, 3, 4] ]’

sample1

The reachable nodes are highlighted in red color. So, the answer is ‘11’.

Test Case 2:
‘n = 3’, ‘m = 7’
‘edges = [ [0, 1, 5], [1, 2, 3] ]’

sample2

The reachable nodes are highlighted in red color. So, the answer is ‘8’.

Sample input 2:

2
5 16 5
1 2 4
2 3 5
3 4 10
1 4 6
2 4 1
4 8 4
0 1 3
0 2 6
1 2 4
1 3 1

Sample output 2:

1
18
Hint

Try to create the new graph from ‘edges’.

Approaches (2)
Breadth-first search traversal of the new graph

Create the new graph from the original graph by adding the chain nodes. The problem becomes finding the number of nodes whose shortest path from node ‘0’ is less than equal to ‘m’. As the new graph is unweighted, we can use Breadth-first search (BFS) traversal to find the shortest path. The shortest path length will be equivalent to the node’s level in the BFS traversal tree. Perform BFS up to level ‘m’, as we only want the nodes with path length less than equal to ‘m’.
 

Proof of correctness: As we move level-wise in BFS, if a child node is not visited, it’s not reachable from any previous levels. Its shortest path will be equal to (parent node’s level + 1). Even if it’s reachable from any other node from the next levels, the corresponding path length will always be greater.
 

Following is an implementation of BFS to solve this problem:
 

  • Set ‘id = n’. Use this as the node number for the chain nodes.
  • Run a loop where ‘i’ ranges from ‘0’ to ‘numOfPairs - 1’:
    • ‘n += edges[i][2]’. Calculate the number of nodes in the new graph by adding the number of chain nodes.
  • Create an adjacency list ‘graph[n]’. Use it to store the new graph.
  • Run a loop where ‘i’ ranged from ‘0’ to ‘numOfPairs - 1’, add the chain nodes:
    • Set ‘l = e[0]’ and ‘r = id’.
    • Run a loop where ‘j’ ranges from ‘0’ to ‘edges[i][2] - 1’:
      • ‘graph[l].append(r)’
      • ‘graph[r].append(l)’
      • ‘id += 1’. The node number for the next node in the chain.
      • ‘l = r’ and ‘r = id’
    • ‘graph[edges[i][1]].append(l)’
    • ‘graph[l].append(edges[i][1])’
  • Create an empty queue ‘bfsQ’. Use it to perform the BFS traversal.
  • Create an array ‘seen[n]’ set to ‘false’. Use it to track visited nodes.
  • ‘bfsQ.push(0)’ and ‘seen[0] = true’. As ‘0’ is the source node.
  • Set ‘res = 1’, and ‘lvl = 0’. Use ‘res’ to store the number of reachable nodes and ‘lvl’ to store the current BFS level.
  • Run a loop while (‘bfsQ’ is not empty) and (‘lvl’ is not equal to ‘m’):
    • Set ‘sz = size(bfsQ)’. Here, ‘sz’ is the number of nodes at level ‘lvl’.
    • Run a loop where ‘i’ ranges from ‘i’ to ‘0’ to ‘sz - 1’. The nodes remaining in ‘bfsQ’ after ‘sz’ iterations belong to the next level:
      • ‘cur = bfsQ.pop()’
      • Run a loop where ‘j’ ranges from ‘0’ to ‘length(graph[cur]) - 1’:
        • ‘next = graph[cur][j]’
        • If ‘seen[next]’ is ‘false’, then we have not visited the node ‘next’:
          • ‘bfsQ.push(next)’
          • ‘seen[next] = true’
          • ‘res++’. Node ‘next’ is reachable from node ‘0’.
    • ‘lvl += 1’. Move to the next level, until level ‘m’.
  • Return ‘res’ as the answer.
Time Complexity

O(N + SZ * NumOfPairs), where ‘N’ is the number of nodes in the given graph, ‘SZ’ is the number of chain nodes in a single edge, and 'NumOfPairs’ is the number of edges.

 

The time complexity for BFS traversal when an adjacency list is used is ‘O(V + E)’, where ‘V’ is the number of vertices and ‘E’ is the number of edges in the graph. In the worst-case scenario, each edge has the maximum number of chain nodes ‘sz’ (i.e., 10 ^ 4 in this problem), so for the new graph, we have ‘V = N + SZ * NumOfPairs’ and ‘E = NumOfPairs + NumOfPairs * SZ’. Hence, the time complexity of ‘O(N + SZ * NumOfPairs)’.

Space Complexity

O(N + SZ * NumOfPairs), where ‘N’ is the number of nodes in the given graph, ‘SZ’ is the number of chain nodes in a single edge, and ‘NumOfPairs’ is the number of edges.

 

Space required by the adjacency list used to store the new graph is ‘O(E)’, the ‘seen’ array is ‘O(E)’, and the ‘bfsQ’ is ‘O(V). Here, ‘V’ is the number of vertices, and ‘E’ is the number of edges. In the worst-case scenario, for the new graph we have ‘V = N + SZ * NumOfPairs’ and ‘E = NumOfPairs + NumOfPairs * SZ’. Hence, the space complexity of ‘O(N + SZ * NumOfPairs)’.

Code Solution
(100% EXP penalty)
Reachable nodes in the new graph
Full screen
Console