题意

给出n个单词，问这n个单词是否可以首尾相连

思路

欧拉道路问题，用dfs解决

把每个单词的首字母和尾字母存到G[][]中，用vis数组记录访问过的次数（因为会有相同的首尾字母，即G[][]>1）,用cnt记录道路的长度。

总结

这个题思路比较清晰，两次敲代码折在了同一个地方就是 G[s[0]-'a'][s[len]-'a']，没加s[]直接写的len-'a'_(:з」∠)_看了好久愣是看不出来，ZZ

 

#include 
     
      #include 
      
       #include 
       
        const int maxn = 1010;int T, n, cnt = 0;int G[30][30], vis[30][30];char s[maxn];using namespace std;void dfs(int u){    cnt++;    for(int v = 0; v < 26; v++){        if(G[u][v] && vis[u][v] < G[u][v]){            vis[u][v]++;            dfs(v);        }    }}int main(){    //freopen("in.txt","r",stdin);    cin >> T;    while(T--){        cin >> n;        getchar();        memset(G, 0, sizeof G);        memset(vis, 0, sizeof vis);        for(int i = 0; i < n; i++){            cin >> s;            int len = strlen(s) - 1;            G[s[0]-'a'][s[len]-'a']++;                    }        bool flag = false;        for(int i = 0; i < 26; i++){            for(int j = 0; j < 26; j++){                if(G[i][j]){ //用每个单词开一次头                    cnt = 0;                    vis[i][j]++;                    dfs(j);                    if(cnt == n) {flag = true; break;}                    memset(vis , 0 ,sizeof vis); //不要忘了数组清零                }            }            if(flag) break;        }        if(flag) cout << "Ordering is possible." << endl;        else cout << "The door cannot be opened." << endl;    }    return 0;}