Problem statement

https://binarysearch.com/problems/Connected-Cities/

Solution

Pretty classical problem, however a bit difficult for medium level. What you need to check here if given graph have only one strongly connected component, we kan use Kosaraju’s Algorithm.

Complexity

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

Code

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

        SCC, S, P, out, D = [], [], [], [0]*n, [0]*n
        st = list(range(n))
        
        while st:
            x = st.pop()
            if x < 0:
                d = D[~x] - 1
                if P[-1] > d:
                    SCC += [S[d:]]
                    del S[d:], P[-1]
                    for x in SCC[-1]: D[x] = -1
            elif D[x] > 0:
                while P[-1] > D[x]: P.pop()
            elif D[x] == 0:
                S += [x]
                P += [len(S)]
                D[x] = len(S)
                st += [~x]
                st += G[x]

        return len(SCC) == 1