地址  https://algospot.com/judge/problem/read/WORDCHAIN

解答:

1 书上的解法是制作有向图 然后查找欧拉回路  代码实现稍后

假设一定存在欧拉路径的做法

#include
#include
#include
#include

using namespace std;

vector> adj;

vector graph[][];

vector indegree, outdegree;

void makeGraph(const vector& words)
{
for (int i = ; i < ; i++) for (int j = ; j < ; j++) graph[i][j].clear(); adj = vector>(, vector(, ));
indegree = outdegree = vector(, );
for (int i = ; i < words.size(); i++) {
int a = words[i][] - 'a';
int b = words[i][words[i].size() - ] - 'a';
graph[a][b].push_back(words[i]);
adj[a][b]++;
outdegree[a]++;
indegree[b]++;
}
}

void getEulerCircuit( int here,vector& circuit )
{
for (int there = ; there < adj.size(); ++there) { while (adj[here][there] > ) {
adj[here][there]--;
getEulerCircuit(there, circuit);
}
}

 circuit.push\_back(here);  

}

vector getEulerTrailOrCircuit()
{
vector circuit;

 for (int i = ; i < ; i++) {  
     if (outdegree\[i\] == indegree\[i\] + ) {  
         getEulerCircuit(i, circuit);  
         return circuit;  
     }  
 }

 for (int i = ; i < ; ++i)  
 {  
     if (outdegree\[i\]) {  
         getEulerCircuit(i, circuit);  
         return circuit;  
     }  
 }

 return circuit;  

}

string solve(const vector& words)
{
makeGraph(words);

 vector<int> circuit = getEulerTrailOrCircuit();

 if (circuit.size() != words.size() + ) return "IMPOSSIBLE";

 reverse(circuit.begin(), circuit.end());  
 string ret;  
 for (int i = ; i < circuit.size(); i++) {  
     int a = circuit\[i - \], b = circuit\[i\];  
     if (ret.size()) ret += " ";  
     ret += graph\[a\]\[b\].back();  
     graph\[a\]\[b\].pop\_back();  
 }

 return ret;  

}

int n, m;
int main()
{
cin >> n;
while (n--) {
cin >> m;
vector words;
while (m--) {
string s;
cin >> s;
words.push_back(s);
}

     cout << solve(words) << endl;

 }

 return ;  

}

先统计有向图的出入度 判断有无欧拉回路与欧拉路径后 在进行dfs的做法

#include
#include
#include
#include

using namespace std;

vector> adj;

vector graph[][];

vector indegree, outdegree;

void makeGraph(const vector& words)
{
for (int i = ; i < ; i++) for (int j = ; j < ; j++) graph[i][j].clear(); adj = vector>(, vector(, ));
indegree = outdegree = vector(, );
for (int i = ; i < words.size(); i++) {
int a = words[i][] - 'a';
int b = words[i][words[i].size() - ] - 'a';
graph[a][b].push_back(words[i]);
adj[a][b]++;
outdegree[a]++;
indegree[b]++;
}
}

void getEulerCircuit(int here, vector& circuit)
{
for (int there = ; there < adj.size(); ++there) { while (adj[here][there] > ) {
adj[here][there]--;
getEulerCircuit(there, circuit);
}
}

 circuit.push\_back(here);  

}

string solve(const vector& words)
{
makeGraph(words);

 int start = -; int end = -;

 for (int i = ; i < ; i++) {  
     if (outdegree\[i\] != indegree\[i\]) {  
         if (outdegree\[i\] == indegree\[i\] +  ) {  
             if (- == start)  
                 start = i;  
             else  
                 return "IMPOSSIBLE";  
         }  
         else if (outdegree\[i\] +  == indegree\[i\] ) {  
             if( - == end)  
                 end = i;  
             else  
                 return "IMPOSSIBLE";  
         }  
     }  
 }

 vector<int> circuit;  
 if (start == - && end == -) {  
     for (int i = ; i < ; ++i)  
     {  
         if (outdegree\[i\]) {  
             getEulerCircuit(i, circuit);  
             break;  
         }  
     }  
 }  
 else {  
     getEulerCircuit(start, circuit);  
 }

 reverse(circuit.begin(), circuit.end());  
 string ret;  
 for (int i = ; i < circuit.size(); i++) {  
     int a = circuit\[i - \], b = circuit\[i\];  
     if (ret.size()) ret += " ";  
     ret += graph\[a\]\[b\].back();  
     graph\[a\]\[b\].pop\_back();  
 }

 return ret;  

}

int n, m;
int main()
{
cin >> n;
while (n--) {
cin >> m;
vector words;
while (m--) {
string s;
cin >> s;
words.push_back(s);
}

     cout << solve(words) << endl;

 }

 return ;  

}

2 个人觉得 可以使用首尾单词作为关键字 去哈希 然后进行哈希查找与DFS结合的搜索 看看最后能否将单词全部使用 代码如下

TLE

#include
#include
#include

using namespace std;

int n, m;

/*
3
4
dog
god
dragon
need
3
aa
ab
bb
2
ab
cd

need dog god dragon
aa ab bb
IMPOSSIBLE
*/

vector ret;

void Dfs( int begIdx,vector>>& vvstr)
{
if (ret.size() == m) {
return;
}

 for (int i = ; i < ; i++) {  
     for (int j = ; j < vvstr\[begIdx\]\[i\].size(); j++) {  
         //选择 nextBegIdx 开头的字母  
         //如果已经选择过了 则进行下一次尝试  
         if (vvstr\[begIdx\]\[i\]\[j\]\[\] == '#')  
             continue;

         //开始选择该单词接龙  
         int nextBegIdx = vvstr\[begIdx\]\[i\]\[j\].back() - 'a';  
         ret.push\_back(vvstr\[begIdx\]\[i\]\[j\]);  
         vvstr\[begIdx\]\[i\]\[j\]\[\] = '#'; //修改字符串的第一个字符 作为已经被选择的标记

         Dfs( nextBegIdx, vvstr);

         if (ret.size() == m) {  
             return;  
         }

         vvstr\[begIdx\]\[i\]\[j\]\[\] = 'a'+ begIdx;  
         ret.pop\_back();  
         break;  
     }  
 }

}

void DfsStart(vector>>& vvstr)
{
for (int i = ; i < ; i++) {
for (int j = ; j < ; j++) {
for (int k = ; k < vvstr[i][j].size(); k++) {
//选中这个单词作为开始
int nextBegIdx = vvstr[i][j][k].back() - 'a';
ret.push_back(vvstr[i][j][k]);
vvstr[i][j][k][] = '#'; //修改字符串的第一个字符 作为已经被选择的标记
Dfs( nextBegIdx,vvstr);

             if (ret.size() == m) {  
                 return;  
             }

             //复原 继续下一次选择  
             vvstr\[i\]\[j\]\[k\]\[\] = 'a'+i;  
             ret.pop\_back();  
             break;  
         }  
     }  
 }

}

int main()
{
cin >> n;
while (n--) {
cin >> m;
string s; vector>> vvstr(, vector>(, vector()));
ret.clear();
for (int i = ; i < m; i++){ cin >> s;
int beg = s[] - 'a';
int end = s.back() - 'a';
vvstr[beg][end].push_back(s);
}
DfsStart(vvstr);
if(!ret.empty()){
for (int i = ; i < ret.size(); i++) {
cout << ret[i] << " ";
}
}
else {
cout << "IMPOSSIBLE";
}
cout << endl;
}

 return ;  

}