top1编程
← 返回题目
题解

骑马修栅栏

1 条题解

  • 0
    @ 2026-7-29 0:20:11
    #include<bits/stdc++.h>
    using namespace std;
    int mp[505][505];
    queue<int> ans;
    int du[505];
    int n=0,m,u,v;
    void dfs(int i)
    {
    	for(int j=1;j<=n;j++)
    	{
    		if(mp[i][j]>=1)
    		{
    			mp[i][j]--;
    			mp[j][i]--;
    			dfs(j);
    		}
    	}
    	ans.push(i);
    }
     
    int main()
    {
    	cin>>m;
    	for(int i=1;i<=m;i++)
    	{
    		cin>>u>>v;
    		mp[u][v]++;
    		mp[v][u]++;
    		du[u]++;
    		du[v]++;
    		n=max(n,max(u,v)); 
    	}
    	int start=1;
    	for(int i=1;i<=n;i++)
    	{
    		if(du[i]%2==1)
    		{
    			start=i;
    			break; 
    		}
    	}
    	dfs(start);
    //	while(!ans.empty())
    //	{
    //		cout<<ans.front()<<endl;
    //		ans.pop();
    //	}
    	int len=ans.size();
    	int ansans[len];
    	int cnt=0;
    	while(!ans.empty())
    	{
    		ansans[cnt++]=ans.front();
    		ans.pop();
    	}
    	for(int i=len-1;i>=0;i--)
    	{
    		cout<<ansans[i]<<endl;
    	}
    	
    	return 0;
    }
    
    • 1