板子

一、有向图欧拉路径 / 回路（最常用）

• 单词接龙

• 字符串拼接

• 边不重复的路径问题

基础板子（裸实现）

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;                      // 边数
vector<int> G[N];           // 邻接表，存边编号
int in[N], out[N];          // 入度、出度
bool used[N];               // 边是否访问过
vector<int> path;           // 最终路径（逆序）
int cur[N];                 // 当前弧优化（防止退化）

// 边集，用于还原终点
int from[N], to[N];

void dfs(int u) {
    for (; cur[u] < G[u].size(); ) {
        int id = G[u][cur[u]++];
        if (used[id]) continue;
        used[id] = true;
        dfs(to[id]);
        path.push_back(id); // 回溯时压栈
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;      // 题目给的是点编号
        G[u].push_back(i);
        from[i] = u;
        to[i] = v;
        out[u]++;
        in[v]++;
    }

    // ---------- 1. 判存在性 ----------
    int start = -1, cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; i++) {
        if (out[i] - in[i] == 1) {
            cnt1++;
            start = i;
        } else if (in[i] - out[i] == 1) {
            cnt2++;
        } else if (abs(in[i] - out[i]) > 1) {
            cout << "No Solution\n";
            return 0;
        }
    }

    if (!(cnt1 == 0 && cnt2 == 0) && !(cnt1 == 1 && cnt2 == 1)) {
        cout << "No Solution\n";
        return 0;
    }

    // ---------- 2. 找起点 ----------
    if (start == -1) {
        for (int i = 1; i <= n; i++) {
            if (out[i]) {
                start = i;
                break;
            }
        }
    }

    // ---------- 3. 字典序最小（关键） ----------
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end(),
             [](int x, int y) {
                 // 按终点字典序，或按边权排序
                 return to[x] < to[y];
             });
    }

    // ---------- 4. Hierholzer ----------
    memset(cur, 0, sizeof(cur));
    dfs(start);

    // ---------- 5. 检查是否用完所有边 ----------
    if (path.size() != n) {
        cout << "No Solution\n";
        return 0;
    }

    // ---------- 6. 逆序输出 ----------
    reverse(path.begin(), path.end());
    for (int i = 0; i < n; i++) {
        cout << path[i] << " ";
    }
    return 0;
}

---

二、无向图欧拉路径 / 回路

• 一笔画

• 街道清扫

• 奇度点判断

 基础板子（裸实现）

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int n;                      // 边数
vector<int> G[N];           // 邻接表，存边编号
int deg[N];                 // 度数
bool used[N];               // 边是否访问过
vector<int> path;           // 路径（逆序）
int cur[N];

// 边集
int u[N], v[N];

void dfs(int x) {
    for (; cur[x] < G[x].size(); ) {
        int id = G[x][cur[x]++];
        if (used[id]) continue;
        used[id] = true;
        // 无向边，下一个点是 u[id]^v[id]^x
        dfs(u[id] ^ v[id] ^ x);
        path.push_back(id);
    }
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> u[i] >> v[i];
        G[u[i]].push_back(i);
        G[v[i]].push_back(i);
        deg[u[i]]++;
        deg[v[i]]++;
    }

    // ---------- 1. 判存在性 ----------
    int start = -1, odd = 0;
    for (int i = 1; i <= n; i++) {
        if (deg[i] % 2 == 1) {
            odd++;
            start = i;
        }
    }

    if (odd != 0 && odd != 2) {
        cout << "No Solution\n";
        return 0;
    }

    // ---------- 2. 找起点 ----------
    if (start == -1) {
        for (int i = 1; i <= n; i++) {
            if (deg[i]) {
                start = i;
                break;
            }
        }
    }

    // ---------- 3. 字典序最小 ----------
    for (int i = 1; i <= n; i++) {
        sort(G[i].begin(), G[i].end());
    }

    // ---------- 4. DFS ----------
    memset(cur, 0, sizeof(cur));
    dfs(start);

    // ---------- 5. 检查 ----------
    if (path.size() != n) {
        cout << "No Solution\n";
        return 0;
    }

    // ---------- 6. 逆序输出 ----------
    reverse(path.begin(), path.end());
    for (int id : path) {
        cout << u[id] << " " << v[id] << "\n";
    }
    return 0;
}

讲解

一、什么是欧拉路径 / 欧拉回路

历史背景

定义

• 欧拉路径（Eulerian Path）：一条路径，经过图中每条边恰好一次

• 欧拉回路（Eulerian Circuit）：一条起点 = 终点的欧拉路径

 注意：欧拉路径关心的是边，不是点。每个点可以经过多次，但每条边只能走一次。

与之对应的是哈密顿路径——经过每个点恰好一次

---

二、无向图的判定定理

设图连通（忽略孤立点），对每个点的度数 deg(v) 分类：

奇度点个数	结论
0	存在欧拉回路​
2	存在欧拉路径（两个奇度点分别是起点和终点）
其他	不存在​

举例

• 三角形 ABC：每个点 deg=2（0 个奇度）→ 欧拉回路 

• 一条链 A—B—C：A、C deg=1，B deg=2（2 个奇度）→ 欧拉路径 A→B→C 

• 星形：中心 deg=4，叶子各 deg=1 → 4 个奇度 

---

三、有向图的判定定理

设图弱连通（把所有边当无向看是连通的），对每个点记：

• out(v)：出度

• in(v)：入度

情况分类

条件	结论
所有点 out = in	欧拉回路​
恰好 1 个点 out − in = 1（起点） 恰好 1 个点 in − out = 1（终点） 其余 out = in	欧拉路径​
其他	不存在​

---

四、构造算法：Hierholzer（主流做法）

核心思想

从起点出发，贪心 DFS，走不动了就往答案里塞当前点，最后逆序输出。

为什么逆序？因为 DFS 先碰到的是"死路"，而死路在欧拉路径里往往是靠后的部分，回溯时倒着加才对。

        伪代码（有向图版）

void dfs(u):
    while 存在边 u->v 未用过:
        标记 u->v 已用
        dfs(v)
    ans.push_back(u)   // 注意是"走不动了才压栈"

最后 reverse(ans) 就是从起点到终点的欧拉路径。

        复杂度

• O(E)，每条边处理一次，非常高效

回溯版 DFS（不是标准 Hierholzer 的逆序压栈，而是正序 choose[acc]=s[i] 直接构造）：

choose[acc+1] = s[i];
vis[i] = 1;
dfs(s[i], acc+1);
vis[i] = 0;

• 找到完整解直接 exit(0)

• 如果序列要正序输出，这种"凑齐 n 条就停"的回溯也对

• 本质是 DFS 枚举 + 欧拉判定提前剪枝，n≤1000 能过

例题

如果单词 X 的末字母与单词 Y 的首字母相同，则 X 与 Y 可以相连成 X.Y。（注意：X、Y 之间是英文的句号 .）。例如，单词 dog 与单词 gopher，则 dog 与 gopher 可以相连成 dog.gopher。

另外还有一些例子：

dog.gopher
gopher.rat
rat.tiger
aloha.aloha
arachnid.dog
连接成的词可以与其他单词相连，组成更长的词链，例如：

aloha.arachnid.dog.gopher.rat.tiger

注意到，. 两边的字母一定是相同的。

现在给你一些单词，请你找到字典序最小的词链，使得每个单词在词链中出现且仅出现一次。注意，相同的单词若出现了 k 次就需要输出 k 次。

输入格式
第一行是一个正整数 n（1≤n≤1000），代表单词数量。

接下来共有 n 行，每行是一个由 1 到 20 个小写字母组成的单词。

输出格式
只有一行，表示组成字典序最小的词链，若不存在则只输出三个星号 ***。

输入输出样例

6
aloha
arachnid
dog
gopher
rat
tiger
 

aloha.arachnid.dog.gopher.rat.tiger
说明/提示
对于 40% 的数据，有 n≤10；
对于 100% 的数据，有 n≤1000。
 

一、问题建模：把单词变成图

1. 抽象成图

• 节点：26 个小写字母 a~z

• 边：每个单词是一条有向边

  • 起点：单词首字母

  • 终点：单词末字母

• 约束：每条边（单词）必须且只能走一次

于是题目变成：

在有向图中，找一条经过所有边恰好一次的路径（欧拉路径 / 欧拉回路），并且拼接出的单词序列字典序最小

---

二、欧拉路径的存在性判定（核心）

对于有向图，欧拉路径存在的充要条件是：

 情况 1：欧拉路径（非回路）

• 有且仅有 1 个点

  • 出度 − 入度 = 1 → 起点

• 有且仅有 1 个点

  • 入度 − 出度 = 1 → 终点

• 其余点：出度 = 入度

 情况 2：欧拉回路

• 所有点：出度 = 入度

• 可从任意点出发

 否则：无解，输出 ***

---

判定逻辑

s1[s[i][0]-'a']++;      // 出度++
s1[s[i][s[i].length()-1]-'a']--; // 入度--

• s1[i] > 0：出度大于入度

• s1[i] < 0：入度大于出度

随后统计：

if(s1[i] == 1) k++, h = i;
if(s1[i] == 2 || k == 2) break;

含义：

• k == 1：找到一个“出度−入度=1”的点 → 唯一合法起点

• k == 0：所有点平衡 → 欧拉回路

• k >= 2 或某个 s1[i] == 2 → 无解

---

三、DFS 构造字典序最小的欧拉路径

1. 为什么要排序？

sort(s+1, s+n+1);

• 题目要求：字典序最小

• 同一起始字母的单词中，优先选字典序小的

• 排序后，DFS 按自然顺序遍历，第一次找到的解就是字典序最小

---

2. 邻接表的“隐式构建”

for(int i = 1; i <= n; i++){
    if(start[s[i][0]-'a'] == 0)
        start[s[i][0]-'a'] = i;
}

• start[c]：首字母为 c 的第一个单词在排序数组中的位置

• DFS 中：

for(int i = start[c_now - 'a']; i; i++){
    if(s[i][0] != c_now) break;
    ...
}

本质是按首字母分组遍历，效率高、代码简洁

隐含前提：排序后，同一首字母的单词连续 —— 成立

---

3. DFS（Hierholzer 算法）

void dfs(string s_now, int acc){
    if(acc == n){ ... exit(0); }

    char c_now = s_now.back();
    for(int i = start[c_now - 'a']; i; i++){
        if(s[i][0] != c_now) break;
        if(vis[i]) continue;

        choose[acc+1] = s[i];
        vis[i] = 1;
        dfs(s[i], acc+1);
        vis[i] = 0; // 回溯
    }
}

• acc：已使用的单词数

• 每次从当前单词的最后一个字母出发

• 找到完整解后立即 exit(0)，保证字典序最小

---

四、起点选择逻辑

情况 A：存在明确起点（k == 1）

for(int i = 1; i <= n; i++){
    if(s[i][0] - 'a' == h){
        dfs(s[i], 1);
    }
}

• 枚举所有首字母为 h 的单词

• 排序保证第一个成功 DFS 的是最优解

情况 B：欧拉回路（k == 0）

for(int i = 1; i <= n; i++){
    dfs(s[i], 1);
}

• 任意单词都可作起点

• 同样，排序保证字典序最小