제출 #1083674

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083674		LouisCheng	어르신 집배원 (BOI14_postmen)	Cpython 3	0 / 100	18 ms	4684 KiB

postmen

import sys
 
# sys.stdin = open("1.in", "r")
 
n, m = map(int, input().split())
paths = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    paths[a].add(b)
    paths[b].add(a)
 
res = []
 
def solve(node):
    while paths[node]:
        top = paths[node].pop()
        paths[top].discard(node)
        solve(top)
    res.append(node)
 
solve(0)
 
last = [len(res)] * n
next = [len(res)] * len(res)
for i in range(len(res) - 1, -1, -1):
    next[i] = last[res[i]]
    last[res[i]] = i
 
nested = [[]]
ends = [len(res) - 1]
for i in range(len(res)):
    if ends[-1] == i:
        ends.pop()
        print(*nested.pop())
        if ends and next[i] < ends[-1]:
            nested.append([res[i] + 1])
            ends.append(next[i])
        continue
    nested[-1].append(res[i] + 1)
    if next[i] < ends[-1]:
        nested.append([res[i] + 1])
        ends.append(next[i])

• Subtask 1: 0 / 38
• Subtask 2: 0 / 17
• Subtask 3: 0 / 45