1129. Shortest Path with Alternating Colors - Explanation

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
        red, blue = defaultdict(list), defaultdict(list)

        for src, dst in redEdges:
            red[src].append(dst)

        for src, dst in blueEdges:
            blue[src].append(dst)

        answer = [-1 for _ in range(n)]
        q = deque()
        q.append((0, 0, None))  # [node, length, prev_edge_color]
        visit = set()
        visit.add((0, None))

        while q:
            node, length, edgeColor = q.popleft()
            if answer[node] == -1:
                answer[node] = length

            if edgeColor != "RED":
                for nei in red[node]:
                    if (nei, "RED") not in visit:
                        visit.add((nei, "RED"))
                        q.append((nei, length + 1, "RED"))

            if edgeColor != "BLUE":
                for nei in blue[node]:
                    if (nei, "BLUE") not in visit:
                        visit.add((nei, "BLUE"))
                        q.append((nei, length + 1, "BLUE"))

        return answer

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
        def buildGraph(edges):
            adj = [[] for _ in range(n)]
            for u, v in edges:
                adj[u].append(v)
            return adj

        red, blue = buildGraph(redEdges), buildGraph(blueEdges)
        adj = [red, blue]
        INF = float("inf")
        dist = [[INF] * 2 for _ in range(n)]
        dist[0][0] = dist[0][1] = 0

        q = deque([(0, 0), (0, 1)])
        while q:
            node, color = q.popleft()
            for nei in adj[color][node]:
                if dist[nei][color ^ 1] > dist[node][color] + 1:
                    dist[nei][color ^ 1] = dist[node][color] + 1
                    q.append((nei, color ^ 1))

        answer = [0] + [-1] * (n - 1)
        for i in range(1, n):
            answer[i] = min(dist[i][0], dist[i][1])
            if answer[i] == INF:
                answer[i] = -1
        return answer

class Solution:
    def shortestAlternatingPaths(self, n: int, redEdges: list[list[int]], blueEdges: list[list[int]]) -> list[int]:
        def buildGraph(edges):
            adj = [[] for _ in range(n)]
            for u, v in edges:
                adj[u].append(v)
            return adj

        red, blue = buildGraph(redEdges), buildGraph(blueEdges)
        adj = [red, blue]
        INF = float("inf")
        dist = [[INF] * 2 for _ in range(n)]
        dist[0][0] = dist[0][1] = 0

        def dfs(node, color):
            for nei in adj[color][node]:
                if dist[nei][color ^ 1] > dist[node][color] + 1:
                    dist[nei][color ^ 1] = dist[node][color] + 1
                    dfs(nei, color ^ 1)

        dfs(0, 0)
        dfs(0, 1)

        answer = [0] + [-1] * (n - 1)
        for i in range(1, n):
            answer[i] = min(dist[i][0], dist[i][1])
            if answer[i] == INF:
                answer[i] = -1

        return answer