24分求助

P2731 [USACO3.3] 骑马修栅栏 Riding the Fences

shaun2000 @ 2024-06-28 19:03:34

#include <bits/stdc++.h>

using namespace std;
vector <int> w[1030];
int t[1030],s=0,e=0;
int book[505][505];
int sum=0,es;
int m;
void dfs(int x,int fa)
{
    book[x][fa]=1;
    book[fa][x]=1;
    printf("%d\n",x);
    if(sum==m)
    {
        return;
    }
    int l=w[x].size();
    for(int i=0; i<l; i++)
    {
        int rc=book[x][w[x][i]];
        if(w[x][i]==fa || rc==1)
            continue;

        if(rc!=e)
        {
            dfs(w[x][i],x);
        }
        else if(es>1)
        {
            dfs(w[x][i],x);
            es--;
        }
        else if(sum+1==m)
        {
            dfs(w[x][i],x);
            es--;
        }

    }
}
int main()
{

    scanf("%d",&m);
    for(int i=1; i<=m; i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        w[x].push_back(y);
        w[y].push_back(x);
        t[x]++;
        t[y]++;

    }
    bool flag=true;
    int F=0;
    for(int i=1; i<=500; i++)
    {
        if(!F)
            F=i;
        if(t[i]%2==1)
        {
            if(s)
            {
                e=i;
                break;
            }
            else
            {
                flag=false;
                s=i;
            }
        }
    }
    es=w[e].size();
    if(flag)
    {
        dfs(F,F);
    }
    else
        dfs(s,s);

    return 0;
}

|