HDU 5348 MZL's endless loop（DFS去奇数度点+欧拉回路）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5348

题目大意：给你一张图，有n个点，和m条无向边，让你把m条无向边变成有向边，使得每个节点的|出度-入度|<=1。

解题思路：先找出所有度数为奇数的点入队，然后依次从这些奇数点开始dfs到另一个奇数点停止。那样就能保证图中是剩下偶数点了，剩下的偶数点肯定会形成欧拉回路（若干个），有套圈法判断路径方向即可。

代码：

 1 #include<iostream>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<cstring>
 5 #define CLR(arr,val)  memset(arr,val,sizeof(arr))
 6 using namespace std;
 7 const int N=1e5+5;
 8 const int M=3e5+5; 
 9 
10 struct node{
11     int next,to,w;
12 }edge[2*M];
13 
14 int n,m,idx;
15 int degree[N],head[N],dir[M];
16 bool vis[M];
17 
18 void init(){
19     idx=2;
20     CLR(head,0);
21     CLR(degree,0);
22     CLR(vis,false);
23 }
24 
25 void addedge(int u,int v,int w){
26     edge[idx].next=head[u];
27     edge[idx].to=v;
28     edge[idx].w=w;
29     head[u]=idx++;
30 }
31 
32 void dfs1(int u){
33     for(int &j=head[u];j;j=edge[j].next){
34         node t=edge[j];
35         if(!vis[j>>1]){
36             vis[j>>1]=true;
37             degree[u]--;
38             degree[t.to]--;
39             dir[j>>1]=t.w;
40             if(degree[t.to]%2==1)
41                 dfs1(t.to);
42             return;                    //注意这里要return 
43         }
44     }
45 }
46 
47 //套圈法找欧拉回路 
48 void dfs2(int u){
49     for(int &j=head[u];j;j=edge[j].next){
50         node t=edge[j];
51         if(!vis[j>>1]){
52             vis[j>>1]=true;
53             degree[u]--;
54             degree[t.to]--;
55             dir[j>>1]=t.w;
56             dfs2(t.to);
57         }
58     }
59 }
60 
61 int main(){
62     int t;
63     scanf("%d",&t);
64     while(t--){
65         init();
66         scanf("%d%d",&n,&m);
67         for(int i=1;i<=m;i++){
68             int u,v;
69             scanf("%d%d",&u,&v);
70             degree[u]++;
71             degree[v]++;
72             addedge(u,v,1);
73             addedge(v,u,0);
74         }
75         queue<int>q;
76         for(int i=1;i<=n;i++){
77             if(degree[i]%2==1)
78                 q.push(i);        //所有奇点入队 
79         }        
80         //消除奇数点
81         while(!q.empty()){
82             int t=q.front();
83             q.pop();
84             if(degree[t]%2==1){
85                 dfs1(t);
86             }        
87         }
88         //找欧拉回路
89         for(int i=1;i<=n;i++){
90             if(degree[i]>0)
91                 dfs2(i);
92         }
93         for(int i=1;i<=m;i++){
94             printf("%d
",dir[i]);
95         }
96     }
97     return 0;
98 }