Pagini recente » Cod sursa (job #2303903) | Cod sursa (job #2252822) | Cod sursa (job #2502222) | Cod sursa (job #399309) | Cod sursa (job #2539122)
"""
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')