AcWing 1124. Solution to the problem of repairing fences on horseback (Euler circuit)

AcWing 1124. Riding a horse to mend the fence
What needs to be remembered is why ans To output in reverse order , And how to search according to the scheme with the smallest dictionary order

Big guy problem solving original address

#include<bits/stdc++.h>

using namespace std;

const int N = 510, M = 1100;

int g[N][N];
int ans[M];
int n = 500, m;
int cnt;
int din[N];

void dfs(int u) {
    
	for(int i = 1; i <= n; i ++ ){
    
		if(g[u][i]){
    
			g[u][i] -- ;
			g[i][u] -- ;
			dfs(i);
		}
	}
	ans[ ++ cnt] = u;
}

int main()
{
    
	cin>>m;
	while(m -- ){
    
		int a, b;
		cin>>a>>b;
		g[a][b] ++ ;
		g[b][a] ++ ;
		din[a] ++ ;
		din[b] ++ ;
	}
	
	int start = 1;
	while(!din[start]) start ++ ;  // Find the first existing point start 
	
	for(int i = 1; i <= n; i ++ ){
    
		if(din[i] % 2){
      // In an undirected graph, only points with odd degrees can be used as starting points  
			start = i;
			break;
		}
	} 
	
	dfs(start);
	
	for(int i = cnt; i; i -- ) cout<<ans[i]<<endl;
	
	return 0;
}