02337: Catenyms

Eulerian Path, http://cs101.openjudge.cn/practice/02337/

A catenym is a pair of words separated by a period such that the last letter of the first word is the same as the last letter of the second. For example, the following are catenyms:

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog

A compound catenym is a sequence of three or more words separated by periods such that each adjacent pair of words forms a catenym. For example,

aloha.aloha.arachnid.dog.gopher.rat.tiger

Given a dictionary of lower case words, you are to find a compound catenym that contains each of the words exactly once.

输入

The first line of standard input contains t, the number of test cases. Each test case begins with 3 <= n <= 1000 - the number of words in the dictionary. n distinct dictionary words follow; each word is a string of between 1 and 20 lowercase letters on a line by itself.

输出

For each test case, output a line giving the lexicographically least compound catenym that contains each dictionary word exactly once. Output "***" if there is no solution.

样例输入

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

样例输出

aloha.arachnid.dog.gopher.rat.tiger
***

来源

Waterloo local 2003.01.25

这是一道经典的图论问题，可以抽象为在有向图中寻找欧拉通路（Eulerian Path）。

算法分析

1. 建图：

   • 将 26 个字母看作图的节点。
   • 每个单词看作从其“首字母”到“尾字母”的一条有向边。
   • 因为题目要求找到字典序最小的解，我们首先将所有单词按字典序进行升序排序。

2. 判断欧拉通路的存在性： 一个有向图存在欧拉通路的条件是：

   • 连通性：忽略边方向后，所有具有边连接的顶点必须在同一个连通分量中。
   • 度数条件：
     • 要么所有节点的入度等于出度（此时存在欧拉回路，起点可以是任意有边节点的最小字母）。
     • 要么恰好有一个节点满足 出度 - 入度 = 1（起点），且恰好有一个节点满足 入度 - 出度 = 1（终点），其余节点入度等于出度。

3. 寻找字典序最小的通路：

   • 为了得到字典序最小的序列，我们使用 Hierholzer 算法（或类似的深度优先搜索 DFS）。
   • 在 DFS 过程中，当一个节点有多个出边时，为了保证最终结果字典序最小，我们需要通过一种巧妙的策略：在 DFS 递归时，按单词字典序从小到大选择边，但为了配合 pop() 操作和后序遍历，我们需要将出边表按字典序升序排列，并从后往前选择（即先选择字典序大的单词进行递归，这样字典序小的单词会最后被处理并最先在反转后的结果中出现）。
   • 更简单的做法：将每个节点的出边（单词）按字典序降序排列，然后每次 pop() 出最后一个单词（即当前最小的单词）进行 DFS，最后将结果列表反转。

4. 最后验证：

   • 如果 DFS 遍历到的边数等于总单词数 $n$，说明找到了覆盖所有单词的路径；否则，说明图不连通，输出 ***。

Python 代码实现

import sys

# 增加递归深度以处理 N=1000 的情况
sys.setrecursionlimit(10000)

def solve():
    # 使用 fast I/O 读取所有输入
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    it = iter(input_data)
    try:
        t_cases = int(next(it))
    except StopIteration:
        return
    
    for _ in range(t_cases):
        try:
            n = int(next(it))
        except StopIteration:
            break
        
        words = []
        for _ in range(n):
            words.append(next(it))
        
        # 1. 字典序排序
        # 我们希望在 DFS 中先走字典序小的边。
        # 配合 pop()，我们将单词按降序排列，这样 pop() 拿到的就是最小的单词。
        words.sort(reverse=True)
        
        adj = [[] for _ in range(26)]
        in_deg = [0] * 26
        out_deg = [0] * 26
        chars_present = [False] * 26
        
        for w in words:
            u = ord(w[0]) - ord('a')
            v = ord(w[-1]) - ord('a')
            adj[u].append(w)
            out_deg[u] += 1
            in_deg[v] += 1
            chars_present[u] = chars_present[v] = True
            
        # 2. 查找起点并检查度数条件
        start_node = -1
        out_minus_in_1 = 0
        in_minus_out_1 = 0
        possible = True
        
        for i in range(26):
            diff = out_deg[i] - in_deg[i]
            if diff == 1:
                out_minus_in_1 += 1
                start_node = i
            elif diff == -1:
                in_minus_out_1 += 1
            elif diff == 0:
                continue
            else:
                possible = False
                break
        
        # 欧拉通路判别
        if not ((out_minus_in_1 == 0 and in_minus_out_1 == 0) or 
                (out_minus_in_1 == 1 and in_minus_out_1 == 1)):
            possible = False

        if not possible:
            print("***")
            continue

        # 如果是欧拉回路，从最小的具有出度的字符开始
        if start_node == -1:
            for i in range(26):
                if out_deg[i] > 0:
                    start_node = i
                    break
        
        # 3. Hierholzer 算法寻找路径
        res_path = []
        
        def dfs(u):
            curr_adj = adj[u]
            while curr_adj:
                # 弹出当前节点最小的单词（因为之前是 reverse 排序）
                w = curr_adj.pop()
                v = ord(w[-1]) - ord('a')
                dfs(v)
                # 后序加入路径
                res_path.append(w)
        
        if start_node != -1:
            dfs(start_node)
        
        # 4. 连通性检查及输出
        if len(res_path) != n:
            print("***")
        else:
            # 路径是后序添加的，需要反转
            print(".".join(reversed(res_path)))

if __name__ == "__main__":
    solve()

关键点总结

• 排序与 DFS 的结合：在 Hierholzer 算法中，想要得到字典序最小的路径，必须在每个节点选择出边时，总是优先选择字典序最小的那条。由于代码使用了 res_path.append(w) 后序添加并最终反转的逻辑，在 while 循环中先选择字典序小的单词进入递归是正确的。
• 连通性：本题中，除了度数判断外，最简单判断连通性的方法就是看最后得到的路径长度是否等于单词总数 $n$。
• 性能：使用 sys.stdin.read().split() 能够极大提高 Python 处理大量单词时的速度。排序复杂度为 $O(N\log N)$，DFS 复杂度为 $O(N)$，整体效率很高。

【孙婧斯、生命科学学院】思路：把单词当作首字母到尾字母的路径，最终应形成要么是一条链，要么是一条环的情况。用并查集判断全局连通性，不连通就提前终止。统计入度出度，如果不符合（一个入点&一个出点&其余点出入度相等）or（所有点出入度相等）的情况，都可以提前终止。

如果判断都通过了，递归构建路径。至于为什么dfs函数中用while而不是if，

假设： a → b → c

​ ↓↑

​ d

如果用if就会忽略掉支路

为了维护字典序最小，需要根据单词对graph中的（边，点）元组排序。因为使用方法是pop()，因此排成逆序。

import sys
sys.setrecursionlimit(10**6)
class UnionFind:
    def __init__(self):
        self.parent=list(range(26))
    def find(self,x):
        if x!=self.parent[x]:
            self.parent[x]=self.find(self.parent[x])
        return self.parent[x]
    def union(self,x,y):
        px,py=self.find(x),self.find(y)
        if px!=py:
            self.parent[px]=py
def dfs(u):
    while graph[u]:
        w,v=graph[u].pop()
        dfs(v)
        path.append(w)

data=sys.stdin.buffer.read().split()
it=iter(data)
t=int(next(it))
for _ in range(t):
    n=int(next(it))
    uf=UnionFind()
    in_degree=[0]*26
    out_degree=[0]*26
    used=[False]*26
    graph=[[] for _ in range(26)]
    for i in range(n):
        word=next(it).decode()
        u=ord(word[0])-97
        v=ord(word[-1])-97
        uf.union(u,v)
        in_degree[v]+=1
        out_degree[u]+=1
        graph[u].append((word,v))
        used[u]=True
        used[v]=True
    for i in range(26):
        graph[i].sort(reverse=True)
    ok=True
    fa=-1
    for i in range(26):
        if used[i]:
            if fa==-1:
                fa=uf.find(i)
            else:
                if uf.find(i)!=fa:
                    ok=False
    start=-1
    inc,ouc=0,0
    for i in range(26):
        if used[i]:
            if in_degree[i]-out_degree[i]==1:
                ouc+=1
            elif in_degree[i]-out_degree[i]==-1:
                inc+=1
                start=i
            else:
                if in_degree[i]-out_degree[i]!=0:
                    ok=False
    if not ((inc==1 and ouc==1) or (ouc==0 and inc==0)):
        ok=False
    if not ok:
        print('***')
    else:
        if start==-1:
            for i in range(26):
                if used[i]:
                    start=i
                    break
        path=[]
        dfs(start)
        if len(path)!=n:
            print('***')
        else:
            print('.'.join(path[::-1]))

这份代码是一个非常标准且高效的欧拉路径（Eulerian Path）算法实现。以下是对该解法的深度解读以及基于原风格的优化建议。

思路解读

1. 图论建模：

   • 点：26个小写字母。
   • 边：每个单词 $word$ 看作从 $word[0]$ 指向 $word[-1]$ 的一条有向边。
   • 目标：寻找一条包含所有边（单词）且字典序最小的路径。

2. 核心判断条件：

   • 连通性：所有出现在单词中的字母必须属于同一个连通分量（用并查集实现）。如果不连通，无法一次性走完所有边。
   • 度数平衡：
     • 欧拉回路（起点终点相同）：所有点的入度等于出度。
     • 欧拉通路（起点终点不同）：恰好有一个点 出度 - 入度 = 1（起点），恰好有一个点 入度 - 出度 = 1（终点），其余点入度等于出度。
   • 如果不满足上述两者之一，则不存在解。

3. 为什么 DFS 中用 while 而不是 if？

   • 这是 Hierholzer 算法 的核心。if 只能让你沿着一条路径走下去，一旦遇到死胡同（虽然在欧拉图逻辑中最后会回到起点，但在处理子环时会出问题）就停止了。
   • while 确保了当一个点有多条出边时，DFS 会递归处理完所有分支（即所有的子环）。在回溯时将边加入 path，保证了即便先进入了某个环，也能正确地将其嵌入主路径中。

4. 字典序保证：

   • 为了得到字典序最小的路径，我们在 DFS 时应优先选择字典序小的单词。
   • 代码逻辑：先对每个点的出边按字典序从大到小排序，然后在 DFS 中使用 pop()。这样每次弹出的都是当前剩余边中字典序最小的那条。

---

优化后的代码

在保持你原有风格的基础上，我进行了如下优化：

1. 增强可读性：规范变量命名（如 start_nodes 代替 inc）。
2. 逻辑收敛：合并一些冗余的判断。
3. 性能微调：利用 Python 的特性简化代码。

import sys

# 增加递归深度，防止深层DFS栈溢出
sys.setrecursionlimit(2000)

class UnionFind:
    def __init__(self):
        self.parent = list(range(26))
    def find(self, x):
        if x != self.parent[x]:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px != py: self.parent[px] = py

def solve():
    # 使用 buffer 快速读取
    data = sys.stdin.buffer.read().split()
    if not data: return
    it = iter(data)
    t = int(next(it))
    
    for _ in range(t):
        n = int(next(it))
        uf = UnionFind()
        in_deg = [0] * 26
        out_deg = [0] * 26
        used = [False] * 26
        graph = [[] for _ in range(26)]
        
        # 存储所有单词，并记录字母出现情况
        for _ in range(n):
            word = next(it).decode()
            u, v = ord(word[0]) - 97, ord(word[-1]) - 97
            graph[u].append((word, v))
            in_deg[v] += 1
            out_deg[u] += 1
            used[u] = used[v] = True
            uf.union(u, v)

        # 1. 字典序排序：降序排列以便 pop() 弹出最小单词
        for i in range(26):
            graph[i].sort(key=lambda x: x[0], reverse=True)

        # 2. 检查全局连通性
        root = -1
        is_connected = True
        for i in range(26):
            if used[i]:
                if root == -1: root = uf.find(i)
                elif uf.find(i) != root:
                    is_connected = False; break
        
        # 3. 检查度数条件并确定起点
        start_node = -1
        out_minus_in_1 = 0 # 出度比入度多1 (起点候选)
        in_minus_out_1 = 0 # 入度比出度多1 (终点候选)
        degree_ok = True
        
        for i in range(26):
            if not used[i]: continue
            diff = out_deg[i] - in_deg[i]
            if diff == 1:
                out_minus_in_1 += 1
                start_node = i
            elif diff == -1:
                in_minus_out_1 += 1
            elif diff != 0:
                degree_ok = False; break
        
        # 欧拉路径条件：要么全相等(0,0)，要么各一个(1,1)
        if not (degree_ok and ((out_minus_in_1 == 0 and in_minus_out_1 == 0) or 
                               (out_minus_in_1 == 1 and in_minus_out_1 == 1))):
            is_connected = False

        if not is_connected:
            print('***')
            continue

        # 如果是欧拉回路，找字典序最小的起始字母
        if start_node == -1:
            for i in range(26):
                if used[i]:
                    start_node = i
                    break
        
        # 4. Hierholzer 算法寻找路径
        path = []
        def dfs(u):
            stack = [u]
            # 这里也可以用递归，但 stack 模拟更稳。
            # 为了保持你的风格，我们沿用递归
            while graph[u]:
                word, v = graph[u].pop()
                dfs(v)
                path.append(word)
        
        # 重新定义内部递归以闭包形式调用，避免重传 graph
        def hierholzer(u):
            while graph[u]:
                w, v = graph[u].pop()
                hierholzer(v)
                path.append(w)

        hierholzer(start_node)

        # 5. 最后验证边数是否完整（应对某些特殊不连通情况）
        if len(path) != n:
            print('***')
        else:
            print('.'.join(path[::-1]))

if __name__ == '__main__':
    solve()

关键点总结：

• Hierholzer 实现：path.append(w) 必须在递归调用之后。这代表“回溯时入栈”。
• 连通性双保险：并查集检查了“点”的连通，最后 len(path) != n 检查了“边”的遍历完整性。
• 排序细节：graph[i].sort(reverse=True) 默认比较元组的第一个元素（即单词字符串），完美符合字典序要求。

问题建模

1. 图的构造
   • 顶点：26 个字母 'a'–'z'。
   • 有向边：每个单词 w 视为一条从 w[0] 指向 w[-1] 的边，边上存储整个单词。
2. 欧拉路径的必要条件
   • 最多一个顶点满足 出度 = 入度 + 1（起点）。
   • 最多一个顶点满足 入度 = 出度 + 1（终点）。
   • 其余顶点都满足 入度 = 出度。
   • 涉及到的所有顶点在“无向”意义上必须连通。
3. 字典序最小
   • 对每个出发字母，用一个 最小堆（heapq）按完整单词排序，取边时总是弹出堆顶，保证当前能选的最小单词优先使用。
4. Hierholzer 算法
   • 从合法的起点（如果不存在“出度 = 入度 + 1”则从最小字母出发）出发，DFS 弹栈构造路径，最后逆序输出。

---

代码实现

import sys
import heapq
from collections import defaultdict, deque


def find_eulerian_path(words):
    indeg = defaultdict(int)
    outdeg = defaultdict(int)
    adj = defaultdict(list)
    used_letters = set()

    # 1. 构造图：入度、出度，并在 adj[u] 中维护 (word, v) 的最小堆
    for w in words:
        u, v = w[0], w[-1]
        outdeg[u] += 1
        indeg[v] += 1
        used_letters |= {u, v}
        heapq.heappush(adj[u], (w, v))

    # 2. 检查度数条件，找可能的起点
    start, plus1, minus1 = None, 0, 0
    for ch in used_letters:
        o, i = outdeg[ch], indeg[ch]
        if o == i + 1:
            plus1 += 1
            start = ch
        elif i == o + 1:
            minus1 += 1
        elif i != o:
            return None
    if not ((plus1 == 1 and minus1 == 1) or (plus1 == 0 and minus1 == 0)):
        return None

    # 3. 如果没有唯一起点，就从最小的有出度的字母开始
    if start is None:
        start = min(ch for ch in used_letters if outdeg[ch] > 0)

    # 4. 连通性检查（无向图）
    seen = {start}
    q = deque([start])
    undirected = defaultdict(list)
    for u in adj:
        for _, v in adj[u]:
            undirected[u].append(v)
            undirected[v].append(u)
    while q:
        u = q.popleft()
        for v in undirected[u]:
            if v not in seen:
                seen.add(v)
                q.append(v)
    if seen != used_letters:
        return None

    # 5. Hierholzer：DFS 弹栈
    path = deque()

    def dfs(u):
        heap = adj[u]
        while heap:
            w, v = heapq.heappop(heap)
            dfs(v)
            path.appendleft(w)

    dfs(start)

    # 6. 检查是否用了所有单词
    if len(path) != len(words):
        return None
    return '.'.join(path)


def solve():
    input = sys.stdin.readline
    t = int(input())
    for _ in range(t):
        n = int(input())
        words = [input().strip() for _ in range(n)]
        ans = find_eulerian_path(words)
        print(ans if ans is not None else "***")


if __name__ == "__main__":
    sys.setrecursionlimit(1000000)
    solve()

• 复杂度：
  • 建图和入度/出度统计：O(N log N)（每个单词入堆）。
  • DFS（Hierholzer）：O(N log N)。
• 能正确处理最大 N=1000 的用例，并保证字典序最小。

"""
https://blog.51cto.com/u_15684947/5384135
"""
from typing import List, Tuple
import sys

class EulerPath:
    def __init__(self):
        self.maxn = 1005
        self.vis = [0] * self.maxn
        self.in_ = [0] * 128
        self.out = [0] * 128
        self.s = [""] * self.maxn
        self.ans = [""] * self.maxn
        self.len_ = [0] * self.maxn
        self.vv = [[] for _ in range(128)]
        self.tot = 0

    def dfs(self, st: str):
        up = len(self.vv[ord(st)])
        for i in range(up):
            cur = self.vv[ord(st)][i]
            if self.vis[cur[1]]:
                continue
            self.vis[cur[1]] = 1
            self.dfs(cur[0][self.len_[cur[1]] - 1])
            self.ans[self.tot] = cur[0]
            self.tot += 1

    def solve(self):
        t = int(input().strip())
        for _ in range(t):
            self.tot = 0
            n = int(input().strip())
            for i in range(1, 128):
                self.in_[i] = self.out[i] = 0
                self.vv[i].clear()
            for i in range(1, n + 1):
                self.vis[i] = 0
                self.s[i] = input().strip()
                self.len_[i] = len(self.s[i])
            minn = 'z'
            for i in range(1, n + 1):
                st = self.s[i][0]
                ed = self.s[i][self.len_[i] - 1]
                self.vv[ord(st)].append((self.s[i], i))
                self.in_[ord(ed)] += 1
                self.out[ord(st)] += 1
                minn = min(minn, ed, st)
            flag = 1
            ru = 0
            chu = 0
            for i in range(ord('a'), ord('z') + 1):
                self.vv[i] = sorted(self.vv[i])
                if not self.in_[i] and not self.out[i]:
                    continue
                if self.in_[i] == self.out[i]:
                    continue
                elif self.in_[i] - self.out[i] == 1:
                    ru += 1
                elif self.out[i] - self.in_[i] == 1:
                    chu += 1
                    minn = chr(i)
                else:
                    flag = 0
                    break
            if flag == 0 or ru > 1 or chu > 1 or ru != chu:
                print("***")
            else:
                self.dfs(minn)
                if self.tot != n:
                    print("***")
                else:
                    for i in range(n - 1, -1, -1):
                        if i != n - 1:
                            print(".", end='')
                        print(self.ans[i], end='')
                    print()

if __name__ == "__main__":
    sys.setrecursionlimit(1000000)
    euler_path = EulerPath()
    euler_path.solve()