Shortest Alternate Colored Path Problem

Given a directed graph consisting of 'N' nodes labeled from '0' to 'N-1'. Each edge in the graph is colored either 'red' or 'blue'. The graph may include self-edges and parallel edges. You have two arrays, redEdges and blueEdges, each containing edges in the form [i, j], representing an edge from node 'i' to node 'j' with the respective color.

The task is to compute an array answer of size 'N', where answer[i] denotes the length of the shortest path from node '0' to node 'i' with alternating colored edges. If no such path exists, answer[i] should be -1.

Input:

The first line contains an integer ‘T’ representing the number of test cases. Each test case begins with three space-separated integers 'N', 'rlen', and 'blen', indicating the number of nodes, and the sizes of the arrays redEdges and blueEdges respectively. The following rlen lines each contain two space-separated integers 'i' and 'j', indicating a 'red' edge. The following blen lines each contain two space-separated integers 'i' and 'j', indicating a 'blue' edge.

Output:

For each test case, output a single line containing 'N' space-separated integers, representing the answer array with the shortest path lengths from node '0' to each node.

Example:

Input:

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

Output:

[0, 1, 2, 2]

Explanation:

The shortest paths from node ‘0’ are:
Node 1: 0-1, Length: 1
Node 2: 0-1-2, Length: 2
Node 3: 0-1-3, Length: 2
Hence, the result array is [0, 1, 2, 2].

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 200

0 ≤ rlen + blen ≤ 1000

Note:

The graph can be disconnected, and there may only be one red or one blue edge between any two distinct nodes. Implementation should only return the results as output is handled separately.

Question

Shortest Alternate Colored Path Problem

Given a directed graph consisting of 'N' nodes labeled from '0' to 'N-1'. Each edge in the graph is colored either 'red' or 'blue'. The graph may include self-edges and parallel edges. You have two arrays, redEdges and blueEdges, each containing edges in the form [i, j], representing an edge from node 'i' to node 'j' with the respective color.

The task is to compute an array answer of size 'N', where answer[i] denotes the length of the shortest path from node '0' to node 'i' with alternating colored edges. If no such path exists, answer[i] should be -1.

Input:

The first line contains an integer ‘T’ representing the number of test cases. Each test case begins with three space-separated integers 'N', 'rlen', and 'blen', indicating the number of nodes, and the sizes of the arrays redEdges and blueEdges respectively.
The following rlen lines each contain two space-separated integers 'i' and 'j', indicating a 'red' edge.
The following blen lines each contain two space-separated integers 'i' and 'j', indicating a 'blue' edge.

Output:

For each test case, output a single line containing 'N' space-separated integers, representing the answer array with the shortest path lengths from node '0' to each node.

Example:

Input:

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

Output:

[0, 1, 2, 2]

Explanation:

The shortest paths from node ‘0’ are:
Node 1: 0->1, Length: 1
Node 2: 0->1->2, Length: 2
Node 3: 0->1->3, Length: 2
Hence, the result array is [0, 1, 2, 2].

Constraints:

1 ≤ T ≤ 100
1 ≤ N ≤ 200
0 ≤ rlen + blen ≤ 1000

Note:

The graph can be disconnected, and there may only be one red or one blue edge between any two distinct nodes. Implementation should only return the results as output is handled separately.

Accepted Answer

The task is to compute the shortest path from node '0' to each node in a directed graph with alternating colored edges.

Create a graph using the given red and blue edges.
Use Breadth First Search (BFS) to find the shortest path from node '0' to each node with alternating colored edges.
If no such path exists, set the length to -1.
Return the array of shortest path lengths for each node.

Accepted Answer

from collections import deque, defaultdict

def shortest_alternating_paths(N, redEdges, blueEdges):
    # Initialize the graph with adjacency lists
    red_graph = defaultdict(list)
    blue_graph = defaultdict(list)
    
    for u, v in redEdges:
        red_graph[u].append(v)
    for u, v in blueEdges:
        blue_graph[u].append(v)
    
    # Initialize the answer array with -1
    answer = [-1] * N
    answer[0] = 0
    
    # Queue for BFS: (node, color, distance)
    queue = deque([(0, 'red', 0), (0, 'blue', 0)])
    
    # Visited states: visited[node][0] for red, visited[node][1] for blue
    visited = [[False, False] for _ in range(N)]
    visited[0][0] = visited[0][1] = True
    
    while queue:
        node, color, distance = queue.popleft()
        
        # Determine the next color and graph to use
        if color == 'red':
            next_color = 'blue'
            next_graph = blue_graph
            color_idx = 1
        else:
            next_color = 'red'
            next_graph = red_graph
            color_idx = 0
        
        for neighbor in next_graph[node]:
            if not visited[neighbor][color_idx]:
                visited[neighbor][color_idx] = True
                queue.append((neighbor, next_color, distance + 1))
                
                if answer[neighbor] == -1:
                    answer[neighbor] = distance + 1
    
    return answer

def solve_test_cases(T, test_cases):
    results = []
    for t in range(T):
        N, rlen, blen, redEdges, blueEdges = test_cases[t]
        result = shortest_alternating_paths(N, redEdges, blueEdges)
        results.append(" ".join(map(str, result)))
    return results

# Example usage with multiple test cases:
T = 1
test_cases = [
    (4, 2, 2, [[0, 1], [2, 3]], [[1, 2], [1, 3]]),
    # You can add more test cases here
]

results = solve_test_cases(T, test_cases)
for result in results:
    print(result)