New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Shortest alternate colored path

Contributed by

Mutiur Rehman khan

Medium

0/80

Avg time to solve 20 mins

Success Rate 80 %

8 upvotes

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]]

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, Constraints, 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 space-separated integers ‘N’, ‘rlen’, and ‘blen’ denoting the number of nodes in the graph, the size of array ‘redEdges’, and the size of array ‘blueEdges’.

The next 'rlen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘red’ edge from node ‘i’ to node ‘j’.

The next 'blen' lines of each test case contain two space-separated integers, ‘i’ and ‘j’ denoting a ‘blue’ edge from node ‘i’ to node ‘j’.

Output format:

For every test case, print a single line containing N space-separated integers denoting array ‘answer’, where ‘answer[i]’ contains the valid shortest path length from node ‘0’ to node ‘i’. 

The output for 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 function.

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:

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]]

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]]

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:

Sample output 2:

0 -1 -1
0 1 1

Auto

Console