【Gym 100812C】Story of Princess (走完图所有边)

BUPT2017 wintertraining(15) #7A

题意

给你一个图，n个点m条边，求走遍所有边，至少经过几次点，及输出依次经过的点。n and m (2 ≤ n ≤ 10^5, 1 ≤ m ≤ 2·10^5)

样例

Input

9 5

2 4

2 6

3 5

3 9

5 9

Output

7

3 9 5 3 6 2 4

Input

4 5

1 2

1 3

1 4

2 4

3 4

Output

6

4 3 1 4 2 1

题解

首先依次从度数为奇数的点出发，走完所有的链。接着把和链相连的环走完，走环的时候用的是走欧拉路径（这里算是欧拉回路）的方法。再把剩下的环走完。

重点是，需要模拟一个链表来连接链和链上的环。

代码

#include <cstdio>

#define N 100005

#define M 400005

using namespace std;

int n,m;

struct edge{

    int to,next;

    bool vis;

}e[M];

int head[N],cnt=2;

int du[N];//点的度数

int idx[N];//点在s中的序号

int ans,sub;//sub是可以减去的步数

int s[M];//存储答案链表

int nxt[M];//nxt[i]代表s[i]在链表中的下一个

void add(int u,int v){

    ++du[u];

    e[cnt]=(edge){v,head[u]};

    head[u]=cnt++;

}

void dfs(int x){

    nxt[ans]=ans+1;

    s[++ans]=x;

    idx[x]=ans;

    for(int &i=head[x];i;i=e[i].next){

        if(e[i].vis)continue;

        e[i].vis=e[i^1].vis=true;

        --du[x],--du[e[i].to];

        dfs(e[i].to);

        break;//每次只找出一条连续的链

    }

}

//找出欧拉回路

void dfs2(int x){

    for(int &i=head[x];i;i=e[i].next){

        if(e[i].vis)continue;

        e[i].vis=e[i^1].vis=true;

        --du[x],--du[e[i].to];

        dfs2(e[i].to);

    }

    nxt[ans]=ans+1;

    s[++ans]=x;

}

int main() {

#ifdef _LOCAL

    freopen("in.txt","r",stdin);

#endif

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

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

        scanf("%d%d",&u,&v);

    add(u,v);add(v,u);

    }

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

        if(du[i]&1)dfs(i);//走完所有的链

#ifdef _LOCAL

    for(int i=1;i<=ans;++i)printf("%d ",s[i]);

    puts("");

#endif

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

    if(idx[i]&&du[i]){//把链上连着的环走完

        int t=ans;

        dfs2(i);

        nxt[idx[i]]=t+2;

        nxt[ans]=idx[i]+1;

        nxt[t]=0;

        ++sub;

    }

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

        if(du[i])dfs2(i);//走完剩下的环

    printf("%d\n",ans-sub);

    if(ans-sub)for(int p=1;p;p=nxt[p])printf("%d ",s[p]);

    return 0;

}

ps：这题我断断续续补了五天，尤其是生日那天，本来希望做出这题来庆祝生日，很惨的是跨越了那天也没有做出来。后来只好看yt的代码才写出来。其实也不是很难啊，就是不容易想到准确的思路，wa了好几天。加油加油啊！！