1913: 【基础】简单单词接龙
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：13
解决：2
题目描述
有n个单词（1≤n≤50），每个单词由2个小写字母组成，并约定第1个单词为龙头。
例如：n=7
7个单词为
aa
ac
ab
de
bh
hk
cd
接龙的方法为前一个单词的第2个字母和后一个单词的第1个字符相同，此时，可接的方法有：
aa—ac—cd 长度为3，即龙上有3个单词
aa—ab—bh—hk 长度为4
程序要求给出单词之后，求出最长龙的长度。
例如：n=7
7个单词为
aa
ac
ab
de
bh
hk
cd
接龙的方法为前一个单词的第2个字母和后一个单词的第1个字符相同，此时，可接的方法有：
aa—ac—cd 长度为3，即龙上有3个单词
aa—ab—bh—hk 长度为4
程序要求给出单词之后，求出最长龙的长度。
输入
第一行一个整数n
接下来n行，每行2个字母表示一个单词（单词字母间无空格）
接下来n行，每行2个字母表示一个单词（单词字母间无空格）
输出
输出一个整数，即最长的接长度（即龙上单词的个数）。
样例输入 复制
7
aa
ac
ab
de
bh
hk
cd样例输出 复制
4提示
#include<bits/stdc++.h>
using namespace std;
#define N 55
int n,cnt,ans=0;
bool used[N];
string w[N];
void dfs(int now,int cnt){
ans=max(ans,cnt);
for(int i=1;i<=n;i++){
if(used[i]!=1&&w[i][0]==w[now][1]){
used[i]=1;
dfs(i,cnt+1);
used[i]=0;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
}
used[1]=1;
dfs(i,1);
cout<<ans;
return 0;
}