Shortest Alternating Path

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
9 upvotes
Asked in companies
GoogleHSBCWalmart

Problem statement

You are given a directed graph 'G' having 'N' nodes. Each node is associated with an integer label from 0 to N - 1. Each edge of this graph is coloured either red or green colour. Your task is to find out for each node in Graph G, it’s shortest alternating distance from the node with label 0.

Note:

1. This Graph may contain self-loops and parallel edges.

2. The Graph will be directed which means it’s edges are one-directional (from some node u to some node v).

3. Alternating distance is the number of edges between two nodes such that the colours of each consecutive edge in the path are different.

4. If there is no alternating path from a node X to the node with label-0 then print -1 as an answer corresponding to that node.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of the input contains an integer 'T', denoting the number of test cases.

The first line of each test case contains three space-separated integers 'N', 'R' and 'G', denoting the number of nodes, number of Red edges and number of Green edges in the graph respectively.

The next 'R' lines of each test case contain two space-separated integers u and v,  denoting Red coloured directed edges from a node with label u to a node with label v.

The next 'G' lines of each test case contain two space-separated integers u and v,  denoting Green coloured directed edges from a node with label u to the node with label v.
Output format: 
For each test case, print a single line containing 'N' space-separated integers denoting the shortest alternating path length of each node from the node with label 0.

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 <= 20
1 <= N, R, G <= 10 ^ 4
0 <= u, v <= N - 1

Time Limit: 1 sec.
Sample Input 1:
1
3 1 1
0 1
1 2
Sample Output 1:
0 1 2
Explanation of sample input 1:
The given graph is as below:

alt-text

In the given graph, it is clearly visible the alternating path distance of nodes from the 0-labelled node are 0, 1 and 2 respectively.
Sample Input 2:
1
3 2 1
0 2
0 1
2 1
Sample Output 2:
0 1 1
Explanation of sample input 2:
The given graph is as below:

alt-text

In the given graph, alternating path lengths of nodes with label 0 and 2 are 0 and 1 respectively. But there are two alternative paths that exist for the node with label 1, but we need to consider only the shorter one, hence the shortest alternating path for the node with label-1 is 1.
Hint

Can you use BFS to check the smallest distance via red and green nodes?

Approaches (1)
BFS Solution
  • We can consider this problem as two graphs each containing edges of only one colour.
  • So, first of all, we form two adjacency lists for graphs with red and green edges only.
  • Now we run Breadth-first search starting from the node with label zero. While doing breadth-first search we will also keep track of the colour of the last encountered edge in the path to some node i.
  • We also make two 2D arrays ‘visited’ and ‘pathLength’ of dimension N * 2.
    • The visited array will keep track if we visited a node ‘i’, via red/green coloured edges or not. It will be initialised with 0 denoting all the nodes as unvisited from both coloured edges.
    • pathLength will store the shortest distance of some node ‘i’ when the last encountered edge in the path is red or green (0 for red and 1 for green). It is initialized with some big integral number MAX (let’s say 10^9) denoting no possible alternating path to that node.
  • Make a queue which will store the vector of size two denoting a label of unprocessed nodes (whose neighbouring nodes are not explored till now) and the last encountered edge in the path.
  • We know that the shortest alternating path to the node with label zero will remain 0 for sure in any situation.
    • Hence we assign ‘0’ to pathLength[0][0] and pathLength[0][1].
    • Also, we will use it as the source node for running the breadth-first search.
    • We push (0,0) and (0,1) into the queue, denoting that we calculated the shortest alternating path to the node with label zero, from both ways(when last encountered edge is red and green).
  • Now we run a loop till the queue of unprocessed nodes with some edge colour will not become empty and do the following steps:
    • First, we get the front node in the queue and remove it from the queue. Let's name it ‘curr”.
    • Now we check the colour of the last encountered edge for the current node.
    • In order to keep the alternating path, we will try to find the next neighbour node of the current node having a different colour from the previous edge colour in the path. Hence we look for the neighbouring unvisited node in the other coloured graph and update their pathLength value and push them into the queue.
  • After processing all the nodes in the queue, we will traverse from 0 to N-1 and take the minimum of pathLength[i][0] and pathLength[i][1]. If this comes out to be MAX(some big integer), then we print -1, else we will print the minimum of these two.
Time Complexity

O(N + R + G), where ‘N’ is the number of nodes, ‘R' is the number of Red edges and ‘G’ is the number of Green edges in the graph.

 

As we are traversing through the Graph exactly once by doing BFS, so it will take the time of the order of O(N + R + G).

Space Complexity

O(N + R + G), where ‘N’ is the number of nodes, ‘R’ is the number of Red edges and ‘G’ is the number of Green edges in the graph.

 

As we are making two adjacency lists, visited and pathLength arrays which take O(N + R + G) order of memory.

Code Solution
(100% EXP penalty)
Shortest Alternating Path
Full screen
Console