Problem statement

https://binarysearch.com/problems/Common-Reachable-Node/

Solution

Reverse edges and compute what elements can be reached from a and from b. Then check that we have non-zero intersection.

Complexity

It is O(n + E) for time and space.

Code

class Solution:
    def solve(self, edges, a, b):
        G = defaultdict(list)
        for x, y in edges:
            G[y] += [x]

        def dfs(node, V):
            V.add(node)
            for neib in G[node]:
                if neib in V: continue
                dfs(neib, V)

        V1, V2 = set(), set()
        dfs(a, V1)
        dfs(b, V2)
        
        return len(V1 & V2) != 0