[CF 528C] Data Center Drama

作法：

首先可以觀察到，在最終的圖裡面每個點的度都會是偶數，因為必須要兩兩捆在一起，所以第一步可以先把所有的奇點都和令一個奇點連一條邊，讓他變成偶點。接下來我們考慮一個邊的序列：從任意一條邊開始，假設他兩端點為 x , y ，然後跳到和這條邊捆在一起的，且有一個端點也是 x 的邊，假設為 x , z ，再跳到和這條邊捆在一起的，且有一個端點是 z 的邊，這樣一直跳下去。因為每條邊都有兩條邊和他捆在一起，所以這個過程會一直進行下去，直到回到原本的 x , y 。觀察在這個序列中邊的方向，因為捆在一起的邊必須要同向，所以可以得到回到 x , y 之後總共的邊數會是偶數，否則會得到 xy 的方向不等於 xy 的方向，矛盾。也就是這樣得到了一個圖中的偶圈。並且反過來也是可以的，也就是當我們找到一個偶圈，那麼就可以沿路把邊的方向定好，讓他滿足條件。所以這又得到了圖中的邊的數量是偶數條，因此如果只有奇數條邊，那麼就還必須要再加一條邊，並且還是滿足每個點的度都是偶數，而這只需隨便對一個點加上一條連到自己的邊就可以了。而題目給的圖又是連通的，這就代表存在一條尤拉迴路，那麼就直接找出這條尤拉迴路，然後把邊的方向都定好就可以了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=500000+10 ;
 
struct P{int x,y;};
vector<P> edge ;
vector<int> v[maxn] ;
int E[maxn],ans[maxm],cnt=0 ;
bool vis[maxm] ;
 
void dfs(int x)
{
    for(int &i=E[x];i<v[x].size();i++) if(!vis[v[x][i]])
    {
        int to=edge[v[x][i]].x==x ?
            edge[v[x][i]].y : edge[v[x][i]].x ;
        int tmp=v[x][i] ;
        vis[v[x][i]]=1 ; i++ ;
        dfs(to) ;
    }
    ans[cnt++]=x ;
}
 
int in[maxn],out[maxn] ;
main()
{
    int n,m ; scanf("%d%d",&n,&m) ;
    for(int i=0;i<m;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        edge.push_back((P){x,y}) ;
        v[x].push_back(i) ;
        v[y].push_back(i) ;
    }
    for(int i=1,last=-1;i<=n;i++) if(v[i].size()%2)
    {
        if(last==-1) last=i ;
        else
        {
            edge.push_back((P){i,last}) ;
            int s=edge.size() ;
            v[i].push_back(s-1) ;
            v[last].push_back(s-1) ;
            last=-1 ;
        }
    }
    if(edge.size()%2)
    {
        edge.push_back((P){1,1}) ;
        int s=edge.size() ;
        v[1].push_back(s-1) ;
        v[1].push_back(s-1) ;
    }
 
    dfs(1) ;
    printf("%d\n",edge.size()) ;
    for(int i=0;i<cnt-1;i++)
    {
        if(i%2==0) printf("%d %d\n",ans[i],ans[i+1]) ;
        else printf("%d %d\n",ans[i+1],ans[i]) ;
    }
}