Cod sursa(job #2532878)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 28 ianuarie 2020 15:59:53
Problema Sortare topologica Scor 80
Compilator py Status done
Runda Arhiva educationala Marime 0.83 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(x, viz, g, sorr):

    viz[x] = True
    for y in g[x]:
        if viz[y] is False:
            dfs(y, viz, g, sorr)
    sorr.append(x)

def solve(n, g, sorr):
    viz = [False for i in range(n + 1)]

    for i in range(1, n + 1):
        if viz[i] == False:
            dfs(i, viz, g, sorr)
    sorr.reverse()

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

    with open('sortaret.out', 'wt') as  fout:
        for x in sorr:
            fout.write('{} '.format(x))
        fout.write('\n')