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

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;
}