P1127 词链 解题报告（欧拉路/欧拉回路判断）

· · 题解

题目链接：https://www.luogu.com.cn/problem/P1127

【题目描述】

如果单词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

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

现在给你一些单词，请你找到字典序最小的词链，使得这些单词在词链中出现且仅出现一次。

【输入格式】

第一行是一个正整数n(1≤n≤1000)，代表单词数量。

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

【输出格式】

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

【解题思路】

欧拉路\欧拉回路判断+dfs

【AC代码】

#include <bits/stdc++.h>
using namespace std;
#define _ 0
int n;
string s[1010];  //记录单词
int Next[1010];  //记录答案序号
bool vis[1010];
int in[30];  //点的入度
int out[30]; //点的出度
inline void QuickSort(register string a[], register int l, register int r)  //手写快排
{
    if (l >= r) return;
    register int low = l;
    register int high = r;
    register string now = a[(l + r) >> 1];
    while (low <= high)
    {
        while (low <= high && a[high] > now) --high;
        while (low <= high && a[low] < now) ++low;
        if (low <= high) swap(a[low++], a[high--]);
    }
    QuickSort(a, l, high);
    QuickSort(a, low, r);
}
inline void dfs(register int pos, register int cnt)  //爆搜，pos表示当前最后一个单词下标，cnt表示已连接单词数目
{
    Next[cnt] = pos;  //记录单词顺序
    if (cnt == n)  //边界条件为已连接单词数目等于n
    {
        for (register int i = 1; i < n; ++i)
        {
            cout << s[Next[i]] << ".";
        }
        cout << s[Next[n]] << endl;
        exit(0);  //直接结束程序
    }
    int l = s[pos].length();
    for (register int i = 1; i <= n; ++i)
    {
        if (!vis[i] && s[pos][l - 1] == s[i][0])
        {
            vis[i] = true;
            dfs(i, cnt + 1);
            vis[i] = false;
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (register int i = 1; i <= n; ++i)
    {
        cin >> s[i];
        ++in[s[i][0] - 'a'];  //首字母的入度++
        ++out[s[i][s[i].length() - 1] - 'a'];  //尾字母出度++
    }
    QuickSort(s, 1, n); //高（搞）效（笑）快排
    register int start = 1;  //记录入度比出度多一的点的序号
    for (register int i = 1; i <= n; ++i)
    {
        if (in[s[i][0] - 'a'] - out[s[i][0] - 'a'] == 1)
        {
            start = i;
            break;
        }
    }
    vis[start] = true;  //别忘了标记一下已经访问（不然会WA）
    dfs(start, 1);  //此时搜索可以保证字典序最小，因为单词已经按字典序排好了
    puts("***");  //程序没结束即为没找到
    return ~~(0^_^0);
}