题目链接:传送门

题目大意:一副无向图,要求你给边定向(变为有向图),使出度等于入度的点最多,输出有多少

     个点,并且输出定向后的边(前为起点,后为终点)

题目思路:欧拉路

     我们这样考虑,先考虑无向图的点的度数,如果为奇数则一定无法变为题目要求的点,ans-1

     对于度为偶数的点则一定可以通过调整满足。

处理方法:新建一个虚拟节点0,使所有度为奇数的点向其连一条边,那么最终图中的点的度数都为偶数。

     这样就满足欧拉路的条件了。我们只需要跑欧拉路并且将走过的路径保留下来即可。

     注意将与虚拟节点连的边删去。

 #include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 1000000007
#define inf 0x3f3f3f3f
#define N 50005
#define maxn 30010
typedef pair<int,int> PII;
typedef long long LL;
LL read(){
LL x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m,k,ans,in[];
int vis[][];
set<int>S[];
vector<PII >V;
void dfs(int u){
while(S[u].size()){
int x=*S[u].begin();S[u].erase(S[u].begin());
if(vis[u][x])continue;
vis[u][x]=vis[x][u]=;
V.push_back(make_pair(u,x));
dfs(x);
}
}
int main(){
int i,j,group,x,y,v,Case=;
group=read();
while(group--){
n=read(),m=read();
mst(in,);V.clear();
mst(vis,);
for(i=;i<=n;++i) S[i].clear();
for(i=;i<=m;++i){
x=read(),y=read();
S[x].insert(y),S[y].insert(x);
++in[x],++in[y];
}
int ans=n;
for(i=;i<=n;++i)if(in[i]&){
--ans;
S[].insert(i),S[i].insert();
}
for(i=;i<=n;++i)
if(S[i].size())
dfs(i);
printf("%d\n",ans);
for(PII u:V)if(u.fi!=&&u.se!=){
printf("%d %d\n",u.fi,u.se);
}
}
return ;
}
05-17 16:21