题意：给你一棵树，让你判断每一条的方向，使每一个节点出度为偶数。 显然，奇数个节点的图一定不符合，偶数个节点的图一定符合。 我们这样构造： 随便选一个根， d f s dfs dfs出一棵生成树。其余边由深度大的点指向深度小的点。 回溯上来，对每一个点现有的出边数目进行讨论。 若为偶数，则由父节点指向本节点，否则由本节点指向父节点。 可以保证根节点也有偶数条出边。 C o d e ： Code： Code：
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int n,m,tot=0,b[N],deep[N],sum[N],blog[N],head[N]; struct node { int vet,nxt,flag; }edge[N]; void add(int u,int v) { edge[++tot].vet=v; edge[tot].nxt=head[u]; head[u]=tot; } void dfs(int u,int fa) { b[u]=1; deep[u]=deep[fa]+1; for(int i=head[u];i;i=edge[i].nxt) { int v=edge[i].vet; if(v==fa)continue; if(!b[v]) { dfs(v,u); if(blog[v]) { edge[i].flag=1; sum[u]++; } }else if(deep[v]<deep[u]) { edge[i].flag=1; sum[u]++; } } if(sum[u]%2==1) { for(int i=head[u];i;i=edge[i].nxt) if(edge[i].vet==fa) { edge[i].flag=1; sum[u]++; break; } }else blog[u]=1; } int main() { scanf("%d%d",&n,&m); if(m%2==1) { puts("-1"); return 0; } for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v);add(v,u); } memset(b,0,sizeof(b)); memset(deep,0,sizeof(deep)); memset(sum,0,sizeof(sum)); memset(blog,0,sizeof(blog)); dfs(1,0); for(int u=1;u<=n;u++) for(int i=head[u];i;i=edge[i].nxt) if(edge[i].flag) printf("%d %d\n",u,edge[i].vet); return 0; }