[CF723E] One-Way Reform

Description

给一张无向图定向，使得有最多的点满足入度等于出度。(T le 200, n le 200, mle 20000)

Solution

建一虚点，将所有奇度点与虚点间连虚边，构造一条欧拉回路，删去所有虚边，即得

（因为度数忘记清零 WA 了若干发）

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 405;
const int dbg = 0;
#define MAXN N

namespace euler
{
stack<int> S;
int edge[MAXN][MAXN];
int n,m,vis[N];
vector<pair<int,int>> ans;

void reset()
{
    memset(edge,0,sizeof edge);
    memset(vis,0,sizeof vis);
}

void dfs(int x)
{
    vis[x]=1;
    S.push(x);
    for(int i=1; i<=n; i++)
    {
        if(edge[x][i]>0)
        {
            edge[i][x]=edge[x][i]=0;
            ans.push_back({x,i});
            dfs(i);
            break;
        }
    }
}

void fleury(int x)
{
    S.push(x);
    while(!S.empty())
    {
        int b=0;
        for(int i=1; i<=n; i++)
        {
            if(edge[S.top()][i]>0)
            {
                b=1;
                break;
            }
        }
        if(b==0)
        {
            S.pop();
        }
        else
        {
            int y=S.top();
            S.pop();
            dfs(y);
        }
    }
}

void make(int p,int q)
{
    edge[p][q]++;
    edge[q][p]++;
}
}

int d[N],edge[N][N];

void solve()
{
    int n,m;
    euler::reset();
    memset(edge,0,sizeof edge);
    memset(d,0,sizeof d);
    cin>>n>>m;
    int t1,t2,tot=0;
    for(int i=1;i<=m;i++)
    {
        cin>>t1>>t2;
        euler::make(t1,t2);
        euler::make(t2,t1);
        edge[t1][t2]=1;
        edge[t2][t1]=1;
        d[t1]++;
        d[t2]++;
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]&1)
        {
            euler::make(n+1,i);
        }
        else
        {
            ++tot;
        }
    }
    cout<<tot<<endl;
    euler::n=n+1;
    for(int i=1;i<=n+1;i++)
    {
        if(euler::vis[i]==0)
        {
            euler::fleury(i);
        }
    }
    for(auto i:euler::ans)
    {
        if(i.first==n+1 || i.second==n+1) continue;
        cout<<i.first<<" "<<i.second<<endl;
    }
    euler::ans.clear();
}

signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}