Cod sursa(job #2536327)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 1 februarie 2020 20:06:53
Problema Componente tare conexe Scor 30
Compilator py Status done
Runda Arhiva educationala Marime 1.22 kb
def read_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)

def dfs(g, used, perm, node):
    used[node] = True
    for x in g[node]:
        if used[x] is False:
            dfs(g, used, perm, x)
    perm.append(node)

def solve(g, gt, n):
    used = {x: False for x in range(1, n + 1)}
    perm = []

    for i in range(1, n + 1):
        if used[i] is False:
            dfs(g, used, perm, i)

    for x in used:  used[x] = False

    scc = []
    perm.reverse()

    for x in perm:
        if used[x] is False:
            new_scc = []
            dfs(gt, used, new_scc, x)
            scc.append(new_scc)
    return scc        

if __name__ == "__main__":
    it = read_gen('ctc.in')
    n, m = next(it), next(it)
    g = {x: [] for x in range(1, n + 1)}
    gt = {x: [] for x in range(1, n + 1)}
    
    for _ in range(m):
        x, y = next(it), next(it)
        g[x].append(y)
        gt[y].append(x)

    scc = solve(g, gt, n)

    with open('ctc.out', 'wt') as fout:
        fout.write('{}\n'.format(len(scc)))
        for scc_comp in scc:
            for node in scc_comp:
                fout.write('{} '.format(node))
            fout.write('\n')