Cod sursa(job #3191632)

Utilizator marinee.anca17@yahoo.comChiricuta Marina Anca [email protected] Data 10 ianuarie 2024 11:06:24
Problema Ciclu Eulerian Scor 10
Compilator py Status done
Runda Arhiva educationala Marime 1.25 kb
def citire(nume_fisier):
    with open(nume_fisier, 'r') as fin:
        N, M = map(int, fin.readline().split())
        G = [[] for _ in range(N + 1)]
        src = [0] * (M + 1)
        dest = [0] * (M + 1)

        for i in range(1, M + 1):
            src[i], dest[i] = map(int, fin.readline().split())
            G[src[i]].append(i)
            G[dest[i]].append(i)

    return N, M, G, src, dest

def conditie_grad_par(G, N):
    return all(len(G[i]) % 2 == 0 for i in range(1, N + 1))

def dfs(nod, G, src, dest, viz, q, poz):
    while poz[nod] < len(G[nod]):
        k = G[nod][poz[nod]]
        poz[nod] += 1
        if not viz[k]:
            viz[k] = True
            dfs(src[k] + dest[k] - nod, G, src, dest, viz, q, poz)

    q.append(nod)

def ciclu_eulerian(N, M, G, src, dest):
    if not conditie_grad_par(G, N):
        return [-1]
    
    viz = [False] * (M + 1)
    poz = [0] * (N + 1)
    q = []
    dfs(1, G, src, dest, viz, q, poz)
    return q

# Exemplu de utilizare
N, M, G, src, dest = citire("ciclueuler.in")
ciclu = ciclu_eulerian(N, M, G, src, dest)
with open("ciclueuler.out", 'w') as fout:
    if ciclu[0] == -1:
        fout.write("-1\n")
    else:
        fout.write(" ".join(map(str, ciclu)) + "\n")