New graph from the SCC

solution_for_gs.py

## Tarjan implementation from Wikipedia's pseudocode
def tarjan(graph):
    #input: graph G = (V, E)
    #output: set of strongly connected components (sets of vertices)
    n = len(graph)
    sccs = []
    index = [0]
    indexes = [-1] * n
    lows = [float('Inf')] * n
    S = []

    def strongconnect(v):
        # Set the depth index for v to the smallest unused index
        indexes[v] = index[0]
        lows[v] = index[0]
        index[0] += 1
        S.append(v)

        # Consider successors of v
        for chld in graph[v]:
            if indexes[chld] == -1:
                # Successor chld has not yet been visited; recurse on it
                strongconnect(chld)
                lows[v] = min(lows[v], lows[chld])
            elif chld in S:
                # Successor w is in stack S and hence in the current SCC
                lows[v] = min(lows[v], lows[chld])

        # If v is a root node, pop the stack and generate an SCC
        if lows[v] == indexes[v]:
            scc = set([v])
            w = S.pop()
            while w != v:
                scc.add(w)
                w = S.pop()
            sccs.append(scc)

    for v in graph.keys():
        if indexes[v] == -1:
            strongconnect(v)

    return sccs

def func_gs():
    INF = float('inf')
    CASES = int(stdin.readline())
    ans = ["-1"] * CASES
    for K in range(CASES):
        stdin.readline()
        graph = read_edge_list_format_graph(directed=True, zerobased=True)

        scc = tarjan(graph)
        ncomp = len(scc)
        sources = set()
        dests = set()
        for incomp in range(ncomp):
            for node in scc[incomp]:
                for edge in graph[node]:
                    for outcomp in range(ncomp):
                        if incomp != outcomp and edge in scc[outcomp]:
                            sources.add(incomp)
                            dests.add(outcomp)
                            break

        sources.difference_update(dests)

        if len(sources) == 1:
            comp = sources.pop()
            ans[K] = str(scc[comp].pop() + 1)

    return " ".join(ans)