Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Shortest alternate colored path

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
17 upvotes
Asked in companies
FlipkartGoogleHSBC

Problem statement

Consider a directed graph of ‘N’ nodes where each node is labeled from ‘0’ to ‘N - 1’. Each edge of the graph is either ‘red’ or ‘blue’ colored. The graph may contain self-edges or parallel edges. You are given two arrays, ‘redEdges’ and ‘blueEdges’, whose each element is of the form [i, j], denoting an edge from node ‘i’ to node ‘j’ of the respective color.

Your task is to compute an array ‘answer’ of size ‘N’, where ‘answer[i]’ stores the length of the shortest path from node ‘0’ to node ‘i’ such that the edges along the path have alternate colors. If there is no such path from node ‘0’ to ‘i’, then ‘answer[i] = -1’.

Example:
N = 4, redEdges = [[0, 1], [2, 3]], blueEdges = [[1, 2], [1, 3]]

example

The shortest paths for each node from node ‘0’ are:
1: 0->1         Length: 1
2: 0->1->2      Length: 2
3: 0->1->3      Length: 2
So, the ‘answer’ array will be: [0, 1, 2, 2].
Note:
1. The given graph could be a disconnected graph.

2. Any two nodes ‘i’ and ‘j’ can have at most one red edge from ‘i’ to ‘j’ and at most one blue edge from ‘i’ to ‘j’.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 100
1 <= N <= 200
0 <= rlen + blen <= 1000

Where ‘T’ is the number of test cases, ‘N’ is the number of nodes in the graph, ‘rlen’ is the size of array ‘redEdges’, and ‘blen’ is the size of array ‘blueEdges’.

Time limit: 1 second

Sample input 1:

2
4 2 2
0 1
1 3
1 1
1 2
4 2 2
0 1
1 3
0 2
2 3

Sample output 1:

0 1 2 3
0 1 1 -1

Explanation of sample input 1:

Test Case 1:

n = 4, redEdges = [[0,1], [1, 3]], blueEdges = [[1, 1], [1, 2]]

Sample1

The shortest paths for each node from node ‘0’ are:
1: 0->1          Length: 1
2: 0->1->2      Length: 2
3: 0->1->1->3   Length: 3
So, the ‘answer’ array will be: [0, 1, 2, 3].


Test Case 2:

n = 4, redEdges = [[0, 1], [1, 3]], blueEdges = [[0, 2], [2, 3]]

Sample2

The shortest paths for each node from node ‘0’ are:
1: 0->1     Length: 1
2: 0->2     Length: 1
3: No valid path available.
So, the ‘answer’ array will be: [0, 1, 1, -1].

Sample input 2:

2
3 1 1
2 1
1 0
3 1 2
1 0
0 1
0 2

Sample output 2:

0 -1 -1
0 1 1
Full screen
Console