AcWing 1184. 欧拉回路 题解（欧拉回路）

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 1e5 + 10, M = 4e5 + 10;
    
    int h[N], e[M], ne[M], idx;
    int ans[M];  //储存答案路径
    int din[N], dout[N];  //储存每个点的入度、出度
    int n, m;
    int type;  //记录图的类型
    int used[M];
    int cnt;  //记录换上有多少边 
    
    void add(int a, int b){
    	e[idx] = b;
    	ne[idx] = h[a];
    	h[a] = idx ++ ;
    } 
    
    void dfs(int u){  //从点开始遍历 
    	for(int &i = h[u]; ~i;){  //i在这里仍然是点的编号,加个&可以避免重复申请空间，节省时间 
    		if(used[i]){
    			i = ne[i];
    			continue;
    		}
    		
    		//标记这条边用过了 
    		used[i] = true;
    		if(type == 1) used[i ^ 1] = true;
    		
    		int t; 
    		//点转化为边 
    		if(type == 1){  //如果是无向图 
    			t = i / 2 + 1;
    			if(i & 1) t = -t;  //如果他是由终点过来的那就是反边 
    		}
    		else t = i + 1;  //如果是有向图，边的编号就是点的编号+1 
    		
    		int j = e[i];
    		i = ne[i];
    		dfs(j);  // 一直走到底 把终点先压进栈 然后回溯往回走把中间及起点加进栈 最终输出结果 ans[cnt]为起点
    		
    		ans[ ++ cnt] = t;
    	}
    }
    
    int main()
    {
    	scanf("%d", &type);
    	scanf("%d%d", &n, &m);
    	memset(h, -1, sizeof h);
    	
    	for(int i = 0; i < m; i ++ ){
    		int a, b;
    		scanf("%d%d", &a, &b);
    		add(a, b);
    		if(type == 1) add(b, a);
    		dout[a] ++ , din[b] ++ ;
    	}
    	
    	//不能构成欧拉图的情况 
    	if(type == 1){  //如果是wu向图 
    		for(int i = 1; i <= n; i ++ ){
    			int t = din[i] + dout[i];
    			if(t & 1){
    				puts("NO");
    				return 0;
    			}
    		}
    	}
    	else{  //如果是you向图 
    		for(int i = 1; i <= n; i ++ ){
    			if(din[i] != dout[i]){
    				puts("NO");
    				return 0;
    			}
    		}
    	}
    	
    	//能构成欧拉图，深搜遍历输出方案
    	
    	for(int i = 1; i <= n; i ++ ){
    		if(h[i] != -1){
    			dfs(i);
    			break;  //找到一个非孤立点就可以开始遍历 
    		}
    	}
    	
    	if(cnt < m){
    		puts("NO");
    		return 0;
    	}
    	
    	cout<<"YES"<<endl;
    	for(int i = cnt; i; i -- ){
    		cout<<ans[i]<<' ';
    	}
    	cout<<endl;
    	return 0;
    }