Luogu p2731 horse riding fence repair

Portal

On the exam, I forgot that I had studied Euler circuit .

It's not difficult to think for yourself , Bidirectional storage map , Set the point with odd degree of finding as the starting point , And then directly dfs search .

then WA The last two points ……

The positive solution is like this ：

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){
	register int x=0,f=1;
	register char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
const int N=1030;
int n;
int vis[N][N];//vis[i][j] Mark i and j Number of paths between  
int cnt[N];// Store the degree of each point  
int maxx,minn=1e9;
int s;// The starting point  
int ans[N],num;
inline void dfs(int x){
	for(register int i(minn);i<=maxx;++i){
		if(vis[x][i]){
			vis[x][i]--,vis[i][x]--;
			dfs(i);
		}
	} 
	ans[++num]=x;// Back save answer  
} 
signed main(){
	n=read();
	for(register int i(1);i<=n;++i){
		int l=read(),r=read();
		vis[l][r]++,vis[r][l]++,cnt[l]++,cnt[r]++;
		maxx=max(maxx,max(l,r));
		minn=min(minn,min(l,r));// Confirm the upper and lower boundaries  
	}
	for(register int i(minn);i<=maxx;++i) if(cnt[i]&1){s=i;break;}// Points with odd degrees must be the starting point or the ending point  
	if(!s) s=minn;// If there is no 
	dfs(s);	
	for(register int i(num);i;--i) printf("%d\n",ans[i]);// Output in reverse order  
	return 0;
} 

WA The storage of code is like this ：

inline void print(){
	printf("%d\n",s);
	for(register int i(1);i<=n;++i) printf("%d\n",ans[i]);
	exit(0);
}
inline void dfs(int x,int num){
	if(num>n) {print();}
	for(register int i(minn);i<=maxx;++i){
		if(vis[x][i]){
			vis[x][i]--,vis[i][x]--;ans[num]=i;
			dfs(i,num+1);
		}
	} 
} 

It doesn't seem to make any difference , Until I made this set of data ：

4

1 2

1 3

1 4

3 4

Drawing shows , Wrong way to find 2 Because of 2 No other Unicom nodes found , So I can't output anything .

Promote it. , Above solution Only serial number priority is guaranteed , The correctness of the current path is not guaranteed .

The backtracking and reverse order output of the positive solution can ensure that the upper layer of recursion is returned in this group of cases , Until the end of the traversal, find the legal answer . And when you go back, you don't vis An array of update , To delete the wrong path directly , Avoid duplicate searches .

Of course, backtracking is stored backwards , Don't forget to lose backwards .

debug victory qwq.