Cod sursa(job #2539122)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 5 februarie 2020 17:44:34
Problema Ciclu Eulerian Scor 20
Compilator py Status done
Runda Arhiva educationala Marime 1.46 kb

"""
    euler cycle property: eulerian cycle can be decomposed into a disjoint set of cycles
    eulerian trevaersal property: if you start from a node you can only get blocked in that node
    (because is the only node with add degree)
    this property makes the trick of sorting nodes by their finish time give a eulerian path
"""

def inp_gen(fname):
    with open(fname, 'rt') as fin:
        for line in fin:
            for val in line.split():
                yield int(val)

def euler(g, n, used, node, cycle):

    for x, edge in g[node]:
        if used[edge] is False:
            used[edge] = True
            euler(g, n, used, x, cycle)
    cycle.append(node)

def solve(g, n, m, euler_path):
    used = {x: False for x in range(m)}
    euler(g, n, used, 1, euler_path)

if __name__ == "__main__":
    it = inp_gen('ciclueuler.in')

    n, m = next(it), next(it)
    ins = {x: 0 for x in range(1, n + 1)}
    g = {x: [] for x in range(1, n + 1)}
    for i in range(m):
        x, y = next(it), next(it)
        g[x].append((y, i))
        g[y].append((x, i))
        ins[x] += 1
        ins[y] += 1

    for i in range(1, n + 1):
        if ins[i] % 2 != 0:
            with open('ciclueuler.out', 'wt') as fout:
                fout.write('{}\n'.format(-1))
                exit(0)

    euler_path = []
    solve(g, n, m, euler_path)
    with open('ciclueuler.out', 'wt') as fout:
        for x in euler_path[:-1]:
            fout.write('{} '.format(x))
        fout.write('\n')