SGU 156 Strange Graph欧拉回路,構想,ハミルトン回路難易度:3

http://acm.sgu.ru/problem.php?contest=0&problem=156
この問題には2つの点がある
1.度数>2団の中の点、必ず1つの度数が2の点を接続する
2.度数が2に等しく、2つの団または1つの団に付着した点を接続する
明らかに度数2の点の2つの辺はすべて歩かなければならなくて、度数>2の点は度数2の点と1つ1つ対応して、使う辺も1つ対応することができて、だからこのハミルトン回路はオラ回路に転化することができます
方法:第1種:新しい図を創立して、簡単ではっきりしています
第2種:オラ路の思想の後続の遍歴を採用して、肝心なのはどのように起点の終点を選んで点跡が回路を形成することができるようにします
度数2の点2辺は必ず歩き終わるので、
度数が2より大きい点を考慮:
このときに対応する度数が2の点が歩かない場合は、先に度数が2の点を行く
それ以外の場合:
経路は団外-団内-団外でなければならないため(団内に複数のステップがあると度数がバランスしない)
前のステップが団外であるか団内であるかを表示し、前のステップが団外である場合、このステップでは団内の度数が2より大きい点を選択できます.
注意:1度数が2より大きい団内点は1度数が2に等しい団外点に対応するが、1個の団外点は2個の団内点に対応するため、直接対応点が団内点遍歴条件として訪問したかどうかは使用できない

#include  <cstdio>

#include <stack>

#include <cstring>

#include <vector>

using namespace std;

const int maxn=1e4+5;

const int maxm=1e5+5;



int n,m,start;

int first[maxn];

int from[2*maxm],to[2*maxm];

int nxt[2*maxm];



int deg[maxn];

int len[maxn];



bool vis[maxn];

int two[maxn];



int ans[maxn],alen;



void addedge(int f,int t,int ind){

        nxt[ind]=first[f];

        to[ind]=t;

        from[ind]=f;

        first[f]=ind;

        deg[f]++;

}

void collect(int s,int f){

        vis[s]=true;

        for(int p=first[s];p!=0;p=nxt[p]){

                int t=to[p];

                if(deg[t]==2){

                        two[s]=t;

                }

                else if(deg[t]>2){

                        if(!vis[t]){

                                collect(t,f);

                        }

                }

        }

        len[f]++;

}

void dfs(int s,bool in){

        vis[s]=true;

     //   printf("reach %d
",s);

        if(deg[s]>2&&!vis[two[s]]){

                dfs(two[s],false);

        }

        for(int p=first[s];p!=0;p=nxt[p]){

                int t=to[p];

                if(vis[t])continue;

                if(deg[s]==2){

                        dfs(t,false);

                }

                else if(!in&&deg[t]>2){

                        dfs(t,true);

                }

        }

        ans[alen++]=s;

    //    printf("exit %d
",s);

}



int main(){

        scanf("%d%d",&n,&m);

        for(int i=1;i<=m;i++){

                int f,t;

                scanf("%d %d",&f,&t);

                addedge(f,t,2*i);

                addedge(t,f,2*i+1);

        }

        for(int i=1;i<=n;i++){

                if(deg[i]>2&&!vis[i]){

                        collect(i,i);

                        if((len[i]&1)!=0){

                                puts("-1");

                                return 0;

                        }

                }

        }

        memset(vis,0,sizeof(vis));



        dfs(1,0);

        if(alen!=n){

                puts("-1");

                return 0;

        }

        for(int i=0;i<n;i++){

                printf("%d ",ans[i]);

        }

        puts("");

        return 0;

}