AcWing 1184. Euler circuit problem solving (Euler circuit)

AcWing 1184. Euler circuit
In this problem, you can directly use penetration 、 The method of judging whether it is Eulerian or not should be remembered , Also remember how to search the path and save the output

#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];  // Save answer path 
int din[N], dout[N];  // Store the penetration of each point 、 The degree of 
int n, m;
int type;  // Type of recording diagram 
int used[M];
int cnt;  // Record how many sides there are  

void add(int a, int b){
    
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx ++ ;
} 

void dfs(int u){
      // Traverse from point  
	for(int &i = h[u]; ~i;){
      //i Here is still the number of points , Add one & It can avoid repeatedly applying for space , Save time  
		if(used[i]){
    
			i = ne[i];
			continue;
		}
		
		// Marking this edge has been used  
		used[i] = true;
		if(type == 1) used[i ^ 1] = true;
		
		int t; 
		// Point to edge  
		if(type == 1){
      // If it's an undirected graph  
			t = i / 2 + 1;
			if(i & 1) t = -t;  // If he comes from the end, it's the opposite side  
		}
		else t = i + 1;  // If it's a digraph , The number of edges is the number of points +1 
		
		int j = e[i];
		i = ne[i];
		dfs(j);  //  Go all the way   Press the end into the stack first   Then go back and add the middle and starting point to the stack   Final output  ans[cnt] As a starting point 
		
		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] ++ ;
	}
	
	// The situation that cannot constitute an eulato  
	if(type == 1){
      // If it is wu Digraph  
		for(int i = 1; i <= n; i ++ ){
    
			int t = din[i] + dout[i];
			if(t & 1){
    
				puts("NO");
				return 0;
			}
		}
	}
	else{
      // If it is you Digraph  
		for(int i = 1; i <= n; i ++ ){
    
			if(din[i] != dout[i]){
    
				puts("NO");
				return 0;
			}
		}
	}
	
	// Can form an Euler chart , Deep search traversal output scheme 
	
	for(int i = 1; i <= n; i ++ ){
    
		if(h[i] != -1){
    
			dfs(i);
			break;  // Find a non isolated point and start traversing  
		}
	}
	
	if(cnt < m){
    
		puts("NO");
		return 0;
	}
	
	cout<<"YES"<<endl;
	for(int i = cnt; i; i -- ){
    
		cout<<ans[i]<<' ';
	}
	cout<<endl;
	return 0;
}