#2,#7,#8WA

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

jinzhaoming @ 2023-11-20 12:25:16

#include <bits/stdc++.h>
using namespace std;
int book[501][501],len,n,start=1,d[501],maxn;
vector<int> a;
void dfs(int x)
{
    a.push_back(x);
    for(int i=1;i<=maxn;i++)
    {
        if(book[x][i]>=1)
        {
            book[x][i]--;
            book[i][x]--;
            dfs(i);
        }
    }
    return ;
}
int main()
{
    int x,y;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>x>>y;
        book[x][y]++;
        book[y][x]++;
        d[x]++;
        d[y]++;
        maxn=max(maxn,max(x,y)); 
    }
    for(int i=1;i<=n;i++)
    {
        if(d[i]%2==1)
        {
            start=i;
            break;
        }
    }
    dfs(start);
    for(int i=0;i<a.size();i++)
        cout<<a[i]<<endl;
    return 0;
}

求dalao指出错误


by duckya @ 2024-01-01 00:06:31

可能有回路,而且不能直接按顺序输出,如果有两个奇点加一个环,有可能两个奇点先结束遍历(这个是看讨论版提到的)。


|