1. 题目

传送门=￣ω￣=

2. 题解

新年新气象，先水一发博客 QvQ

先废话一下，这题标签有个 “虚树”。。。

真 jb 欺骗我感情。。。

要找最长接龙，显然就是个最长路

建图的话哈希一下就行了

怎么哈希一个字符串呢？

我们用一个 $26\times 3$位的数字表示一个字符串，数字前 3 位表示字符串中’a’ 出现了多少次，4,5,6 位表示’b’ 出现了多少次。。。依次类推

比如字符串 “abc” 的哈希值为：
$001001001000000000000000000000000000000000000000000000000000000000000000000000$

QvQ

至于为什么是 3 位的话，因为字符串长度小于等于 100, 所以不可能超过 3 位

很显然没有那种类型能存下这么大的数字，于是我们来哈希取模。

模数推荐：$14233333$

然后跑 spfa。

首先把每个字符串都加入到队列中（就是在枚举起点）。

对于一个字符串，它的哈希值为 $a$，那么可以接龙到它后面的字符串的哈希值为 $a+1,a+100,a+10000,a+1000000…$，这样枚举下一个字符串的哈希值就能转移了。

代码如下（目前跑得是最快的）：

#include <bits/stdc++.h>

#define NS (10005)
#define MS (105)
#define MOD (14233333ll)

using namespace std;

int n, cnt[26], len[NS], h[NS], htab[MOD], dis[NS], pre[NS], ans, mx;

bool book[NS];

char str[NS][MS];

queue<int> que;

stack<int> st;

int main(int argc, char const* argv[])
{
    while (~scanf("%s", str[++n])); n--;
    for (int i = 1; i <= n; i += 1)
    {
        len[i] = strlen(str[i]), memset(cnt, 0, sizeof(cnt));
        for (int j = 0; j < len[i]; j += 1)cnt[str[i][j] - 'a']++;
        for (int j = 0; j < 26; j += 1)
            h[i] = ((100ll * h[i] % MOD) + cnt[j]) % MOD;
        htab[h[i]] = i, que.push(i), dis[i] = book[i] = 1;
    }
    while (!que.empty())
    {
        int F = que.front(); que.pop(), book[F] = 0;
        for (int i = 0, tot = 1, nxt; i < 26; i += 1, tot = 100ll * tot % MOD)
            if (htab[(h[F] + tot) % MOD])
                if (nxt = htab[(h[F] + tot) % MOD], dis[nxt] < dis[F] + 1)
                {
                    dis[nxt] = dis[F] + 1, pre[nxt] = F;
                    if (!book[nxt]) que.push(nxt), book[nxt] = 1;
                }
    }
    for (int i = 1; i <= n; i += 1) if (ans < dis[i]) mx = i, ans = dis[i];
    while (mx) st.push(mx), mx = pre[mx];
    printf("%d\n", ans);
    while (!st.empty()) puts(str[st.top()]), st.pop();
    return 0;
}