Even Degrees_牛客博客

$Description$
给定一个无向图,构造一个有向图使得每个点的出度为偶数.

$Solution$
对这个图生成的树,从叶子结点往上分配,如果该节点的出度为偶数了那么指向根的边当做根的出度,如果是奇数那么指向根的那条边当作该节点的出度.
在子节点满足条件后,判断根结点指向的那个结点是否遍历过如果遍历过那么说明子节点已经满足了,这时这条边当作根的出度.

$Code$

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
template<typename T>int o(T x){cout<<x<<endl;return 0;}
int n,m;
vector<int>g[N];
vector<int>du(N,0);
vector<int>depth(N,-1);
vector<pair<int,int> >p;
int main(){
        cin>>n>>m;
        for(int i=1;i<=m;i++){
                int u,v;
                scanf("%d%d",&u,&v);
                g[u].push_back(v);
                g[v].push_back(u);
        }
        if(m&1)return o(-1);
        function<void(int u,int fa)>dfs=[&](int u,int fa){
                depth[u]=depth[fa]+1;
                for(int v:g[u]){
                        if(depth[v]==-1){
                                dfs(v,u);
                        }else{
                                if(depth[v]>depth[u]){
                                        p.emplace_back(u,v);
                                        du[u]++;
                                }
                        }
                }
                if(fa==0)return;
                if(du[u]&1){
                        p.emplace_back(u,fa);
                        du[u]++;
                }else{
                        p.emplace_back(fa,u);
                        du[fa]++;
                }
        };
        depth[0]=0;
        dfs(1,0);
        for(auto x:p)cout<<x.first<<" "<<x.second<<endl;
}