SGU 156 Strange Graph 欧拉回路,思路,汉密尔顿回路难度:3

http://acm.sgu.ru/problem.php?contest=0&problem=156

这道题有两种点

1. 度数>2 在团中的点,一定连接一个度数为2的点

2. 度数等于2,连接两个团或者附着在一个团上的点

明显度数为2的点的两条边都是要走的,度数>2的点与度数2的点一一对应,所用的边也可以一一对应,所以这道哈密尔顿回路可以转化成欧拉回路

方法:第一种:建立新图,简单清晰

第二种:采用欧拉路的思想后续遍历,关键在怎样选取起点终点使得点迹可以形成回路

度数为2的点两条边肯定都要走完,

考虑度数大于2的点:

如果这时对应的度数为2的点没有走,那么先去度数为2的点

否则:

因为路径必须为团外-团内-团外(如果在团内有多步,那么度数就不平衡)

所以要标注上一步是在团外还是团内,如果上一步是在团外,那么这一步就可以选择一个团内的度数大于2的点

注意:一个度数大于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\n",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\n",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;

}

巴特西

SGU 156 Strange Graph 欧拉回路,思路,汉密尔顿回路难度:3

最新文章

热门文章

巴特西

SGU 156 Strange Graph 欧拉回路,思路,汉密尔顿回路 难度:3

最新文章

热门文章

SGU 156 Strange Graph 欧拉回路,思路,汉密尔顿回路难度:3