为什么将高赞题解用Python实现会RE最后四个点?求大佬解答
查看原帖
为什么将高赞题解用Python实现会RE最后四个点?求大佬解答
871882
Ezreal666楼主2023/3/23 23:18
# 求有向图字典序最小的欧拉路径
import sys


def dfs(u):
    i = d[u]  # 从点u的第一条(i=0)边开始搜索
    total = len(G[u])
    while i < total:
        d[u] = i+1  # 之后走点u的下一条边
        dfs(G[u][i])  # 继续搜索点u的邻点
        i = d[u]  # 点u的第i条边走过了,不再重复走
    rec.append(u)


n, m = map(int, input().split())
du = [[0]*2 for _ in range(n+5)]  # 记录点的入度和出度
G = [[] for _ in range(n+5)]  # 用邻接表存图
d = [0 for _ in range(n+5)]  # d[u]=i:当前走点u的第i个边
rec = []  # 记录欧拉路

for i in range(m):
    u, v = map(int, input().split())
    G[u].append(v)
    du[u][1] += 1  # 点u的出度加1
    du[v][0] += 1  # 点v的入度加1
for i in range(1, n+1):
    G[i].sort()  # 对每个点的邻居点按字典序排序

S = 1  # 起点
cnt = [0, 0]
flag = False
for i in range(1, n+1):
    if du[i][1] != du[i][0]:
        flag = True  # 存在入度不等于出度的点
        if du[i][1] - du[i][0] == 1:
            S = i  # 出度比入度多1,可以作为欧拉路起点
            cnt[1] += 1
        elif du[i][0] - du[i][1] == 1:
            # 入度比出度多1,可以作为欧拉路终点
            cnt[0] += 1
        else:
            print("No")
            sys.exit(0)
if flag and not (cnt[0] == cnt[1] and cnt[0] == 1):
    print("No")
    sys.exit(0)

dfs(S)
for i in range(len(rec)-1, -1, -1):  # 欧拉路与dfs回溯的顺序相反
    print(rec[i], end=' ')

2023/3/23 23:18
加载中...