【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

4 5

1 2

1 3

1 4

3 4

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了好幾天。加油加油啊！！

┆涼┆暖┆降┆等┆幸┆我┆我┆裡┆将┆　┆可┆有┆謙┆戮┆那┆　┆大┆始┆　┆然┆

┆薄┆一┆臨┆你┆的┆還┆沒┆　┆來┆　┆是┆來┆遜┆沒┆些┆　┆雁┆終┆　┆而┆

┆　┆暖┆　┆如┆地┆站┆有┆　┆也┆　┆我┆　┆的┆有┆精┆　┆也┆沒┆　┆你┆

┆　┆這┆　┆試┆方┆在┆逃┆　┆會┆　┆在┆　┆清┆來┆準┆　┆沒┆有┆　┆沒┆

┆　┆生┆　┆探┆　┆最┆避┆　┆在┆　┆這┆　┆晨┆　┆的┆　┆有┆來┆　┆有┆

┆　┆之┆　┆般┆　┆不┆　┆　┆這┆　┆裡┆　┆沒┆　┆殺┆　┆來┆　┆　┆來┆