相关题目: P1127 词链

现象： 开O2 9pts，关O2 AC

代码如下:

#include <cstdio>
#include <string>
#include <iostream>
#include <algorithm>
#define atn(x) (x - 96)
// 小写字母转换为1-26
using namespace std;
const int MAXN = 1e3;
int n, num, s, e, fa[26], ans[MAXN], tp;
// num:连通块个数, fa[] 并查集, ans答案栈, tp栈顶

struct node
{
    int exist, nxt, imdg, exdg;
    // imdg:入度, exdg:出度
} nd[27];

struct edge
{
    string val;
    int nxt, to, vst;
} ed[MAXN | 1];
// 链式前向星存储

inline int cmp(edge x, edge y)
{
    return x.val < y.val;
}

inline int find(int x)
{
    while (fa[x] != x)
        x = fa[x] = fa[fa[x]];
    return x;
}

inline void INIT()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> ed[i].val;
    return;
}

inline void nein()
{
    cout << "***";
    exit(0);
}

inline void PRE()
{
    sort(ed + 1, ed + n + 1, cmp);
    for (int i = 1; i <= 26; ++i)
        fa[i] = i;
    for (int i = n; i; --i)
    {
        int u = atn(ed[i].val.front());
        int v = atn(ed[i].val.back());
        if (find(u) != find(v))
            fa[find(u)] = find(v);
        ++nd[u].exdg, ++nd[v].imdg;
        nd[u].exist = nd[v].exist = 1;
        ed[i].nxt = nd[u].nxt;
        ed[i].to = v;
        nd[u].nxt = i;
    }
    // 预处理:排序、连边
    for (int i = 1; i <= 26; ++i)
        if (nd[i].exist && fa[i] == i)
            ++num;
    if (num != 1)
        nein();
    // 判断连通块个数
    for (int i = 1; i <= 26; ++i)
        if (nd[i].exist)
        {
            if (nd[i].exdg == nd[i].imdg + 1)
            {
                if (s) nein();
                else s = i;
            }
            else if (nd[i].imdg == nd[i].exdg + 1)
            {
                if (e) nein();
                else e = i;
            }
            else if (nd[i].imdg != nd[i].exdg)
                nein();
        }
    if (!(s || e))
        while (!nd[s].exist)
            ++s;
    else if (!(s && e))
        nein();
    // 判断是否为欧拉图
    return;
}

inline void PUT()
{
    cout << ed[ans[0]].val;
    for (int i = 1; i < tp; ++i)
        cout << '.' << ed[ans[i]].val;
    exit(0);
}

void dfs(int x)
{
    for (register int i = nd[x].nxt; i; i = ed[i].nxt)
    {
        if (ed[i].vst)
            continue;
        ed[i].vst = 1;
        ans[tp++] = i;
        if (tp == n)
            PUT();
        dfs(ed[i].to);
        --tp;
        ed[i].vst = 0;
    }
    return;
}

int main()
{
    ios::sync_with_stdio(false);
    INIT();
    PRE();
    dfs(s);
    nein();
}

希望得知该代码厌氧的原因，避免未来再出问题...