Editorial for Pondo Euler Tour

Use this editorial only when stuck, and do not copy-paste code from it.

Please be respectful to the problem author and editorialist. Submitting an official solution before solving the problem yourself is a bannable offence.

Approach

Root the tree at vertex $1$ and run a depth-first search. Append a vertex to the tour when the search enters it, recurse on its neighbours in increasing order (skipping the parent), then append it again when the search leaves. Every vertex is written twice, so the tour has length $2n$ .

Building the adjacency lists and running the search both take $O(n)$ time after sorting neighbours, which is $O(n \log n)$ in the worst case (a star).

Solution (Python)

Code 1

import sys

sys.setrecursionlimit(1_000_000)

data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
adj = [[] for _ in range(n)]
idx = 1
for _ in range(n - 1):
    u = data[idx] - 1
    v = data[idx + 1] - 1
    idx += 2
    adj[u].append(v)
    adj[v].append(u)

for u in range(n):
    adj[u].sort()

tour = []


def dfs(u, p):
    tour.append(u + 1)
    for v in adj[u]:
        if v != p:
            dfs(v, u)
    tour.append(u + 1)


dfs(0, -1)
print(*tour)

Comments0

No comments yet

Be the first to comment.

Editorial for Pondo Euler Tour

Approach

Solution (Python)

Comments0

New comment