Codeforces Round #375 (Div. 2)E. One-Way Reform

题目链接：传送门

题目大意：一副无向图，要求你给边定向（变为有向图），使出度等于入度的点最多，输出有多少

　　　　　个点，并且输出定向后的边（前为起点，后为终点）

题目思路：欧拉路

　　　　　我们这样考虑，先考虑无向图的点的度数，如果为奇数则一定无法变为题目要求的点，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 ;

 }

巴特西

Codeforces Round #375 (Div. 2)E. One-Way Reform

最新文章

热门文章