rt，评测记录

简述题意：找出一条词链使得，前一个词末字母等于后一个词首字母，中间用 . ，隔开，每个单词恰好出现一次。输出字典序最小的词链，若无则输出 ***

对拍了好久也没找到hack数据，也下不了数据，相关讨论里头提到的的所有hack数据都试了一遍，都没找到问题。希望大佬帮个忙，感谢

代码的思路是欧拉路， 基本上是在抄这篇题解

#include <bits/stdc++.h>

using namespace std;

const int N = 1e3 + 10;

string s[N], res[N];
int in[30], out[30], fa[N];
bool v[30], le[30];
int n;
struct Node
{
	int End, ord;
	string str;
};
vector<vector<Node> > E;

int Find(int x)
{
    if (x == fa[x]) return x;
    return fa[x] = Find(fa[x]);
}

void dfs(int x, int now, int Last)
{
    //cout << x << ' ' << now << ' ' << Last << endl;
    if (now == n)
    {
        for (int i = 1; i <= n; ++i)
        {
            cout << res[i];
            if (i < n) cout << '.';
        }
        exit(0);
    }

    for (int i = 0; i < E[x].size(); ++i)
    {
        if (!v[E[x][i].ord])
        {
            v[E[x][i].ord] = true;
            res[now + 1] = E[x][i].str;
            dfs(E[x][i].End, now + 1, E[x][i].ord);
        }
    }
    v[Last] = false;
}
int main()
{
    //freopen("date.in", "r", stdin);
    //freopen("date.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> s[i];
	sort(s + 1, s + 1 + n);

    E.resize(27);
    int TheNumberOfSet = 0;
	for (int i = 1; i <= n; ++i)
	{
		int ChStart = s[i][0] - 'a' + 1;
		int ChEnd = s[i][s[i].size() - 1] - 'a' + 1;
		if (!le[ChStart])
			le[ChStart] = true, ++TheNumberOfSet, fa[ChStart] = ChStart;
		if (!le[ChEnd])
			le[ChEnd] = true, ++TheNumberOfSet, fa[ChEnd] = ChEnd;
		++out[ChStart], ++in[ChEnd];
        if (ChStart != ChEnd)
        {
            int ss = Find(ChStart), ee = Find(ChEnd);
            if (ss != ee) fa[ee] = ss, --TheNumberOfSet;
        }
        E[ChStart].push_back({ChEnd, i, s[i]});
	}
	if (TheNumberOfSet != 1)
    {
        cout << "***";
        //cout << 11111 << endl;
        return 0;
    }
    //cout << 1111 <<endl;
    int EularStart = 0, EularEnd = 0;
    for (int i = 1; i <= 26; ++i)
    {
        if (!le[i]) continue;

        if (out[i] == in[i] + 1)
        {
            if (EularStart)
            {
                cout << "***";
                //cout << 22222 << endl;
                return 0;
            }
            else EularStart = i;
        }
        else if (out[i] == in[i] - 1)
        {
            if (EularEnd)
            {
                cout << "***";
                //cout << 33333 << endl;
                return 0;
            }
            else EularEnd = i;
        }
        else if (in[i] == out[i]) continue;
        else
        {
            cout << "***";
            //cout << 44444444 << endl;
            return 0;
        }
    }
    if ((!EularStart&&EularEnd)||(EularStart&&!EularEnd))
    {
        cout << "***";
        //cout << 555555 << endl;
        return 0;
    }
    if (!EularStart) EularStart = s[1][0] - 'a' + 1;
    //cout << 11111 << endl;
    dfs(EularStart, 0, 0);
	return 0;
}