Problem description
Consider a directed graph, with nodes labelled 0, 1, …, n-1. In this graph, each edge is either red or blue, and there could be self-edges or parallel edges.
Each [i, j] in red_edges denotes a red directed edge from node i to node j. Similarly, each [i, j] in blue_edges denotes a blue directed edge from node i to node j.
Return an array answer of length n, where each answer[X] is the length of the shortest path from node 0 to node X such that the edge colors alternate along the path (or -1 if such a path doesn’t exist).
Example 1:
Input: n = 3, red_edges = [[0,1],[1,2]], blue_edges = [] Output: [0,1,-1] Example 2:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[2,1]] Output: [0,1,-1] Example 3:
Input: n = 3, red_edges = [[1,0]], blue_edges = [[2,1]] Output: [0,-1,-1] Example 4:
Input: n = 3, red_edges = [[0,1]], blue_edges = [[1,2]] Output: [0,1,2] Example 5:
Input: n = 3, red_edges = [[0,1],[0,2]], blue_edges = [[1,0]] Output: [0,1,1]
Solution
This problem can be solved using Breadth First Search.
- For each node, we build its red and blue neighbors.
- We start from node 0 and visited each of its neighbor. If we go through a red edge to v, we will color v as red, else we will color v as blue
- For each subsequent node, if it is red, we only look for blue edges and color its neighbor as blue. Else, we only look for red edges and color its neighbor as red.
- Each step, we add a level by 1. (We only record the result if the node is first time seen).
- To keep us from doing infinity loop, we must keep track of all the edges that we went through, if in step 2,3,4 we saw an edge that we have previously went through, we must skip that edge.
Below is my python implementation
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: List[List[int]], blue_edges: List[List[int]]) -> List[int]:
'''
BFS
'''
rednei = collections.defaultdict(list)
bluenei = collections.defaultdict(list)
for edge in red_edges:
rednei[edge[0]].append(edge[1])
for edge in blue_edges:
bluenei[edge[0]].append(edge[1])
ans = [-1 for i in range(n)]
queue = collections.deque()
queue.append((0, 'grey', 0))
found = set([]) #edges found
while queue:
x, color, level = queue.popleft()
if ans[x] == -1:
ans[x] = level
if color != 'red' and color != 'blue':
for nei in rednei[x]:
if str(x)+'_'+str(nei)+'_'+'red' not in found:
queue.append((nei, 'red', level + 1))
found.add(str(x)+'_'+str(nei)+'_'+'red')
for nei in bluenei[x]:
if str(x)+'_'+str(nei)+'_'+'blue' not in found:
queue.append((nei, 'blue', level + 1))
found.add(str(x)+'_'+str(nei)+'_'+'blue')
elif color == 'red':
for nei in bluenei[x]:
if str(x)+'_'+str(nei)+'_'+'blue' not in found:
queue.append((nei, 'blue', level + 1))
found.add(str(x)+'_'+str(nei)+'_'+'blue')
elif color == 'blue':
for nei in rednei[x]:
if str(x)+'_'+str(nei)+'_'+'red' not in found:
queue.append((nei, 'red', level + 1))
found.add(str(x)+'_'+str(nei)+'_'+'red')
return ans