题解 P2731 【骑马修栅栏 Riding the Fences】

蒟蒻Jason周 · 2019-08-12 20:48:59 · 题解

这就是一道很水的一笔划问题

//P2731
#include<bits/stdc++.h>//懒人最爱，大家别学 
using namespace std;
int e[510][510],ot[510],m,n,u,v,st[60000],top=0;

函数部分：

int dfs(int u){
    for(int i=1;i<=n;i++){
        if(e[u][i]){//判断 
            e[u][i]--;
            e[i][u]--;
            dfs(i);
        }
    }
    st[++top]=u;
    return 0;
}

主函数

int main(){
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>u>>v;//读入 
        ot[u]++;
        ot[v]++;
        if(u>n)n=u;
        if(v>n)n=v;
        e[u][v]++;
        e[v][u]++;
    }
    bool flag=0;
    for(int i=1;i<=n;i++){
        if((ot[i]&1)==1){
            dfs(i);
            flag=1;
            break;
        }
    }
    if(!flag)dfs(1);
    while(top)cout<<st[top--]<<endl;//输出
    return 0;//完美结束 
}

谢谢观看

蒟蒻的题解，如果有任何问题，欢迎提出，看不懂的就看看别人的吧