2
我試圖解決Petersen Graph問題沒有任何成功。這段代碼有什麼問題？你可能會說這不是一個有效的解決方案，沒關係。在這裏，我爲給定的圖形做DFS。爲什麼這段代碼給出Petersen Graph（codechef）的WA？
sruct ss包含圖表。每個String都保存在Set中，每當遞歸終止時就會產生一個輸出。我無法找到這種方法失敗的測試案例。你能否給我一個這種方法會失敗的測試用例？
#include<bits/stdc++.h>
using namespace std;
struct ss{
int p;
int a[3];
char s[3];
};
string get(int k){
switch(k){
case 0:return "0";
case 1:return "1";
case 2:return "2";
case 3:return "3";
case 4:return "4";
case 5:return "5";
case 6:return "6";
case 7:return "7";
case 8:return "8";
case 9:return "9";
}
}
void traverse(string s,ss z[10],int index, set<string> &s1,string s2,int v){
int p = s[index]-'A',i,j;
if(v!=-1)s2 +=get(v);
if(!s[index]){
s1.insert(s2);
return;
}
if(v==-1){
traverse(s,z,index+1,s1,s2,z[2*p].p);
traverse(s,z,index+1,s1,s2,z[2*p+1].p);
}
else{
if(v>=5){v = v-5;v = 2*v+1;}
for(i=0;i<3;i++){
if(z[v].s[i]==s[index]){
traverse(s,z,index+1,s1,s2,z[v].a[i]);
break;
}
}
for(j=0;j<3;j++){
if(z[v].s[j]==s[index]){
traverse(s,z,index+1,s1,s2,z[v].a[j]);
break;
}
}
}
}
int main(){
string s;
set<string> s1;
int t;
ss z[ ]={
{0,{1,4,5},{'B','E','A'}},
{5,{0,7,8},{'A','C','D'}},
{1,{0,2,6},{'A','C','B'}},
{6,{1,8,9},{'B','D','E'}},
{2,{1,3,7},{'B','D','C'}},
{7,{2,5,9},{'C','A','E'}},
{3,{2,4,8},{'C','E','D'}},
{8,{3,5,6},{'D','A','B'}},
{4,{0,3,9},{'A','D','E'}},
{9,{4,6,7},{'E','B','C'}}
};
cin>>t;
while(t--){
s1.clear();
cin>>s;
traverse(s,z,0,s1,"",-1);
if(s1.end()==s1.begin()){
cout<<-1<<"\n";
}
else
cout<<*s1.begin()<<"\n";
}
}