Đề bài: Đồ thị có hướng n đỉnh (0..n-1), cạnh màu đỏ/xanh. Tìm đường đi ngắn nhất từ 0 đến mọi đỉnh sao cho màu cạnh xen kẽ (đỏ-xanh-đỏ... hoặc xanh-đỏ-xanh...). Trả về mảng độ dài, -1 nếu không đến được.
Ví dụ: n=3, red=[[0,1],[1,2]], blue=[] → [0,1,-1] (0→1 đỏ, 1→2 đỏ → không xen kẽ).
Ý tưởng: BFS Trạng Thái (node, color)
Trạng thái = (node, last_color) với last_color ∈ {0: red, 1: blue, 2: start}. Từ trạng thái này, chỉ đi cạnh màu khác last_color.
Chạy BFS từ (0, 2) (start, không có màu trước). Distance đến (v, c) là độ dài đường đi. Kết quả cho đỉnh v = min distance trên 2 màu.
Code Python
from collections import deque
class Solution:
def shortestAlternatingPaths(self, n: int, red_edges: list[list[int]], blue_edges: list[list[int]]) -> list[int]:
# Build adjacency list per color
red_adj = [[] for _ in range(n)]
blue_adj = [[] for _ in range(n)]
for u, v in red_edges:
red_adj[u].append(v)
for u, v in blue_edges:
blue_adj[u].append(v)
# dist[node][color] = shortest distance ending with color
# color: 0=red, 1=blue
INF = float('inf')
dist = [[INF, INF] for _ in range(n)]
dist[0][0] = dist[0][1] = 0 # Start at node 0 with "no previous color" → both 0
# Queue: (node, last_color)
q = deque([(0, 0), (0, 1)]) # Start with both virtual colors
visited = set([(0, 0), (0, 1)])
while q:
node, last_color = q.popleft()
next_color = 1 - last_color # Must alternate
# Choose adjacency based on next_color
neighbors = red_adj[node] if next_color == 0 else blue_adj[node]
for nei in neighbors:
if (nei, next_color) not in visited:
visited.add((nei, next_color))
dist[nei][next_color] = dist[node][last_color] + 1
q.append((nei, next_color))
# Result: min of two colors for each node
res = []
for i in range(n):
d = min(dist[i])
res.append(d if d != INF else -1)
return res
# Test
ob = Solution()
print(ob.shortestAlternatingPaths(3, [[0,1],[1,2]], [])) # [0, 1, -1]
print(ob.shortestAlternatingPaths(3, [[0,1]], [[1,2]])) # [0, 1, 2] (red then blue)
print(ob.shortestAlternatingPaths(3, [[0,1],[0,2]], [[1,0]])) # [0, 1, 1]
Phân tích
- Time:
O(n + E)(E = tổng cạnh đỏ + xanh) - Space:
O(n + E) - BFS đảm bảo shortest path vì trọng số = 1.
Kết luận
Mở rộng trạng thái BFS thêm dimension "màu cạnh cuối" để enforce ràng buộc xen kẽ. Pattern phổ biến cho shortest path với constraint.