本文共 1347 字，大约阅读时间需要 4 分钟。

        给一个无向图（其实是有向的，但是没有指定边的方向），你需要指定边的方向，使得每个点入度和出度相差不超过1。

        其实就是找许多条路径，合起来能走完这个图。。先统计各个顶点的度，度为奇数必是起点或终点，否则是中间点或者同为起点和终点。邻接表建图（建双向），先从每个奇数度顶点出发找路径，再从偶数度顶点出发找路径，经过的边要删去不然超时。

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;const int MAXM=300010;const int MAXN=200010;struct edge{ int u,v;}edges[MAXM*2];int head[MAXN];int pre[MAXM*2];int Next[MAXM*2];int deg[MAXN];int ans[MAXM];int ecnt;int n,m;int init(){ memset(head,-1,sizeof(head)); memset(Next,-1,sizeof(Next)); memset(deg,0,sizeof(deg)); ecnt=0;}void addedge(int u,int v){ edges[ecnt].u=u; edges[ecnt].v=v; pre[ecnt]=head[u]; head[u]=ecnt; ecnt++; // edges[ecnt].u=v; edges[ecnt].v=u; pre[ecnt]=head[v]; head[v]=ecnt; ecnt++;}void dfs(int u){ while(head[u]!=-1){ deg[u]--; int i=head[u]; int v=edges[i].v; if(i&1){ ans[(i>>1)+1]=0; }else{ ans[(i>>1)+1]=1; } //remove edges. int pp,nn; if(head[u]==i){ head[u]=pre[i]; } pp=pre[i]; nn=Next[i]; if(pp!=-1)Next[pp]=nn; if(nn!=-1)pre[nn]=pp; int _i=i^1; if(head[v]==_i){ head[v]=pre[_i]; } pp=pre[_i]; nn=Next[_i]; if(pp!=-1)Next[pp]=nn; if(nn!=-1)pre[nn]=pp; u=v; if(deg[v])deg[v]--; }}int main(){ int t; cin>>t; while(t--){ init(); cin>>n>>m; for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); deg[u]++; deg[v]++; } for(int i=0;i
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/squee_spoon/article/details/47282299 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！