当前位置：网站首页>AcWing 1124. 骑马修栅栏题解（欧拉回路）

AcWing 1124. 骑马修栅栏题解（欧拉回路）

2022-07-21 20:03:00 【QingQingDE23】

AcWing 1124. 骑马修栅栏
需要记住的是为什么ans要按逆序输出，还有如何按字典序最小的方案去搜索
请添加图片描述
大佬题解原地址

#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 ++ ;  //找到第一个存在的点start 
	
	for(int i = 1; i <= n; i ++ ){
    
		if(din[i] % 2){
      //无向图中只有度数为奇数的点可以作为起点 
			start = i;
			break;
		}
	} 
	
	dfs(start);
	
	for(int i = cnt; i; i -- ) cout<<ans[i]<<endl;
	
	return 0;
}