Sponsored
Sponsored
Use a Breadth-First Search (BFS) to traverse the graph, keeping track of the last edge color used (red or blue). This can be done using a queue where each element is a tuple containing the current node, distance traveled, and the color of the edge used to arrive at this node. We need two visited arrays to track if a node has been visited with a red edge or a blue edge to avoid re-processing.
Time Complexity: O(n + redEdges.length + blueEdges.length) - This accounts for the BFS traversal and the construction of adjacency lists.
Space Complexity: O(n) - This is the space required for visited sets and the BFS queue.
1from collections import deque
2
3class Solution:
4 def shortestAlternatingPaths(self, n: int, redEdges: List[List[int]], blueEdges: List[List[int]]) -> List[int]:
5 adj_red = [[] for _ in range(n)]
6 adj_blue = [[] for _ in range(n)]
7 for u, v in redEdges:
8 adj_red[u].append(v)
9 for u, v in blueEdges:
10 adj_blue[u].append(v)
11
12 answer = [-1] * n
13 answer[0] = 0
14 queue = deque([(0, 0, None)])
15 visited_red = set()
16 visited_blue = set()
17
18 while queue:
19 node, dist, last_color = queue.popleft()
20
21 if last_color != 'red':
22 for nei in adj_red[node]:
23 if nei not in visited_red:
24 visited_red.add(nei)
25 if answer[nei] == -1:
26 answer[nei] = dist + 1
27 queue.append((nei, dist + 1, 'red'))
28
29 if last_color != 'blue':
30 for nei in adj_blue[node]:
31 if nei not in visited_blue:
32 visited_blue.add(nei)
33 if answer[nei] == -1:
34 answer[nei] = dist + 1
35 queue.append((nei, dist + 1, 'blue'))
36
37 return answerThe solution first constructs adjacency lists for red and blue edges. A deque is used for BFS which starts from node 0 with a distance of 0. For each node, it checks the next possible nodes via red or blue edges, ensuring no repeated visits are made using the same edge color. It updates the shortest distance for each node when it is first reached, ensuring paths alternate between red and blue.
This approach involves using two separate BFS queues to handle paths starting with red and blue edges. By maintaining distinct queues for red and blue path exploration, the solution ensures color alternation by construction, processing nodes layer by layer from each starting color queue separately.
Time Complexity: O(n + redEdges.length + blueEdges.length) - The layer processing replicates BFS traversal cost.
Space Complexity: O(n) - Needed for separate visitation states and queue management.
1import java.util.*;
2
3
This Java implementation operates with two BFS queues dedicated for red and blue starting paths. The strategy processes node connections based on the opposite color adjacency list, alternatively updating shortest paths. Each queue contributes towards a layer of nodes processed, ensuring paths alternate colors efficiently with minimized total distances computed.