···

’‘’
求解字典序最小的欧拉路径
‘’‘

from collections import Counter
class MergeSetExt:
def init(self, max_key_val = 0, trans_key_func=None):
if trans_key_func is not None and max_key_val > 0:
# 如果能够提供转换key的回调，并查集内部用线性表存储
self.trans_key_callback = trans_key_func
self.m = [-1 for _ in range(max_key_val+1)]
self.__root2cluster_size = [0 for _ in range(max_key_val+1)]
else:
# 如果不能提供转换key的回调，并查集内部用hash表存储
self.trans_key_callback = None
self.m = {}
self.__root2cluster_size = {}
self.__root_cnt = 0

def getRoot(self, node):
    buf = []
    root = self.trans_key_callback(node) if self.trans_key_callback else node
    while self.m[root] != root:
        buf.append(root)
        root = self.m[root]
    for key in buf:
        self.m[key] = root

    return root

def merge(self, a, b):
    orig_a, orig_b = a, b
    if self.trans_key_callback:
        a, b = self.trans_key_callback(a), self.trans_key_callback(b)

    for node in [a, b]:
        if (self.trans_key_callback is None and node not in self.m) or (self.trans_key_callback is not None and self.m[node] == -1):
            self.m[node] = node
            self.__root2cluster_size[node] = 1
            self.__root_cnt += 1

    root1 = self.getRoot(orig_a)
    root2 = self.getRoot(orig_b)
    if root1 != root2:
        self.m[root1] = root2

        self.__root2cluster_size[root2] += self.__root2cluster_size[root1]
        if self.trans_key_callback:
            self.__root2cluster_size[root1] = 0
        else:
            self.__root2cluster_size.pop(root1)
        self.__root_cnt -= 1


def getRootNum(self):
    return self.__root_cnt

class Hierholzer:
# 点序号为1, 2, 3, … node_num
def init(self, edges, node_num):
self.edges = edges[::]
self.node_num = node_num

# 返回欧拉路径，loop_path为True时候返回欧拉回路, keep_min_order为True时候保持路径的字典序最小
def getEulerPath(self, loop_path=False, keep_min_order=False):

    # 判断是否有欧拉路径，返回可能的起点
    def __get_start_nodes(edges):
        if len(edges) == 0:
            return True

        node2degree = Counter()
        merge_set = MergeSetExt(max_key_val=self.node_num, trans_key_func=lambda x : x)
        for (a, b) in edges:
            node2degree[a] += 1
            node2degree[b] += 1
            merge_set.merge(a, b)

        if merge_set.getRootNum() != 1:
            return False

        odd_nodes = []
        for node, degree in node2degree.items():
            if degree & 1:
                odd_nodes.append(node)

        if len(odd_nodes) != 0 and len(odd_nodes) != 2:
            return None

        if loop_path:
            return [node for node in node2degree.keys()] if len(odd_nodes) == 0 else None
        else:
            return odd_nodes if len(odd_nodes) == 2 else [node for node in node2degree.keys()]


    start_nodes = __get_start_nodes(self.edges)
    if start_nodes is None:
        return None

    if len(self.edges) == 0:
        return []

    curPath, loop = [], []
    link = {}
    for (a, b) in self.edges:
        if a not in link:
            link[a] = {}
        if b not in link:
            link[b] = {}

        if b not in link[a]:
            link[a][b] = 1
        else:
            link[a][b] += 1

        if a not in link[b]:
            link[b][a] = 1
        else:
            link[b][a] += 1

    if len(link) == 1:
        # 只有一个点的特殊情况，肯定全部都是自环，特殊处理
        node = None
        for key in link:
            node = key
            break

        return [node] * (len(self.edges) + 1)

    # 无向图不论是求欧拉路径还是欧拉回路，都可以随便选一个起点
    curNode = start_nodes[0] if keep_min_order == False else min(start_nodes)
    edge_cnt = -1  # 累计已经找的边的数量

    visited = set()
    while edge_cnt < len(self.edges):
        curPath.append(curNode)

        if curNode in visited:
            # 找到新的环，进行退栈
            while len(curPath):
                node = curPath[-1]
                if len(link[node]) > 0:
                    if not keep_min_order:
                        next = None
                        for key in link[node].keys():
                            next = key
                            break
                    else:
                        next = min(link[node].keys())

                    link[node][next] -= 1
                    if link[node][next] == 0:
                        link[node].pop(next)

                    link[next][node] -= 1
                    if link[next][node] == 0:
                        link[next].pop(node)

                    curNode = next
                    break
                else:
                    curPath.pop(-1)
                    loop.append(node)
                    edge_cnt += 1
        else:
            visited.add(curNode)

            if len(link[curNode]) > 0:
                if not keep_min_order:
                    next = None
                    for key in link[curNode].keys():
                        next = key
                        break
                else:
                    next = min(link[curNode].keys())

                link[curNode][next] -= 1
                if link[curNode][next] == 0:
                    link[curNode].pop(next)

                link[next][curNode] -= 1
                if link[next][curNode] == 0:
                    link[next].pop(curNode)

                curNode = next
            else:
                curPath.pop(-1)

    return loop[::-1]

import sys
m = int(input())
edges = []
for i in range(m):
s = sys.stdin.readline()
a, b = map(int, s.split())
edges.append((a, b))

algo = Hierholzer(edges, node_num=500)
path = algo.getEulerPath(loop_path=False, keep_min_order=True)
for node in path:
print(node)

···