Problem statement

https://binarysearch.com/problems/Direct-Closure/

Solution

Just run dfs to find connected components and then create answer.

Complexity

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

Code

class Solution:
    def solve(self, G):
        comps, seen, it, n = defaultdict(list), set(), 0, len(G)

        def dfs(node, i):
            comps[i].append(node)
            seen.add(node)
            for neib in G[node]:
                if neib not in seen: dfs(neib, i)

        for j in range(n):
            if j not in seen:
                dfs(j, it)
                it += 1

        ans = [[0] * n for _ in range(n)]
        for x in comps:
            for i, j in product(comps[x], comps[x]):
                ans[i][j] = 1

        return ans