CF723E One-Way Reform

很有意思的一个题，刚开始想复杂了后面看了题解才发现是个傻逼题

首先不难发现答案的上界数就是度数为偶数的节点数，考虑一种构造方法能打到这个上界

不妨新建一个虚拟节点，将所有度数为奇数的点与其连边，这样图中所有点度数都变成了偶数，包括这个虚拟节点

而对于一个所有点度数均为偶数的图，我们知道它一定存在欧拉回路，并且欧拉回路一定会使得进入某个点的次数和离开某个点的次数相等

因此这种方案一定能到达理论上界，复杂度\(O(n^2)\)

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=205;
int t,n,m,x,y,G[N][N],deg[N],vis[N];
inline void DFS(CI now)
{
	for (RI i=0;i<=n;++i) if (G[now][i])
	{
		if (now&&i) printf("%d %d\n",now,i);
		--G[now][i]; --G[i][now]; DFS(i);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
		scanf("%d%d",&x,&y),++deg[x],++deg[y],++G[x][y],++G[y][x];
		int cnt=0; for (i=1;i<=n;++i) if (deg[i]&1) ++G[0][i],++G[i][0]; else ++cnt;
		for (printf("%d\n",cnt),i=0;i<=n;++i) DFS(i);
		for (i=0;i<=n;++i) deg[i]=vis[i]=0;
	}
	return 0;
}