Codeforces 62 D. Wormhouse

問題

n個の部屋と,部屋と部屋を結ぶ通路m本により出来ている家がある。
虫が、m回の移動でちょうど全ての通路を通り、元の部屋へ戻ってくる。

この移動経路がm+1個の部屋番号によって与えられるとき、
m回の移動でちょうど全ての通路を通り元の部屋へ戻ってくるような移動で、
与えられた移動経路よりも辞書順で真に大きく、かつ辞書順最小であるようなものを求めよ。

存在しない場合はNo solutionを出力せよ。

制約条件

n≦100
m≦2000
移動経路において、最初の部屋番号と最後の部屋番号は等しい。

方針

元のスタートの部屋からスタートして、深さ優先探索により、辞書順で元の移動よりも大きい移動があるかどうかを探索する。
これは数字を頭から見ていくDPのような感じで、greaterのフラグを持ちながら探索すればいい。

全ての部屋を訪れることが出来た場合それが答えで、
出来なかった場合、元のグラフに次数が奇数である頂点が2個ある場合と0個ある場合で場合分けする。

次数が奇数である頂点が0個だった場合、どこの頂点から出発しても一筆書き可能なので、元の出発点+1の部屋から出発して一筆書きすればいい。
元の出発点がn番だったらno solution
次数が奇数である頂点が2個だったら、次数が奇数である頂点から一筆書きしなければならないので、
もう一方の次数の奇数の頂点（これが最初の出発点よりも番号が小さかったらno solution）から一筆書きすればいい。

ソースコード

int n,m;
vector<vi> g;
int ans[2001],in[2001];
set<pair<int,int> > used;

bool dfs(int c,int d,bool greater){
  ans[d]=c;
  if(d==m)return c==in[0]&&greater;
  
  rep(i,g[c].size())if(!used.count(mp(c,g[c][i]))&&!used.count(mp(g[c][i],c))
    &&(greater||g[c][i]>=in[d+1])){
    bool ng=greater;
    if(g[c][i]>in[d+1])ng=1;
    used.insert(mp(c,g[c][i]));
    if(dfs(g[c][i],d+1,ng))return 1;
    used.erase(mp(c,g[c][i]));
  }
  return 0;
}
bool solve(){
  used.clear();
  if(dfs(in[0],0,0))return 1;
  
  int a=in[0]+1;
  for(;a<n;a++)if(g[a].size()%2)break;
  if(a==n)return 0;
  
  used.clear();
  return dfs(a,0,1);
  if(in[0]==n-1)return 0;
  
  used.clear();
  return dfs(in[0]+1,0,1);
}
void run(){
  cin>>n>>m;
  g=vector<vi>(n);
  int p,c;
  rep(i,m+1){
    cin>>c; in[i]=--c;
    if(i)g[c].pb(p), g[p].pb(c);
    p=c;
  }
  rep(i,n)sort(all(g[i]));
  
  if(solve()){
    rep(i,m+1)cout<<ans[i]+1<<(i==m?"\n":" ");
  }
  else cout<<"No solution"<<endl;
}