随笔-141  评论-9  文章-3  trackbacks-0
USACO 3.3.1 Riding the Fences(欧拉路, DFS)


这道题是要求我们求出一条欧拉路，所以我们要首先判断图中是否有欧拉路。

对于一个无向图，如果它每个点的度都是偶数，那么它存在一条欧拉回路；

如果有且仅有2个点的度为奇数，那么它存在一条欧拉路；
如果超过2个点的度为奇数，那么它就不存在欧拉路了。

/*
ID: lorelei3
TASK: fence
LANG: C++
*/

#include <fstream>
#include <stack>

using namespace std;

const int MAX = 505;

int map[MAX][MAX];
int degree[MAX];
stack<int> ans;

int n;

inline int max(int a, int b){
    return a>b? a: b;
}

void Eular(int k){
    for(int i=1; i<=n; ++i)
        if(map[k][i]){
            map[k][i]--;
            map[i][k]--;
            Eular(i);
        }
    ans.push(k);
}

int main(){
    int i,c,a,b;

    ifstream fin("fence.in");
    ofstream fout("fence.out");

    fin>>c;

    n = 0;
    for(i=0; i<c; ++i){
        fin>>a>>b;
        map[a][b]++;
        map[b][a]++;
        degree[a]++;
        degree[b]++;
        n = max(n, a);
        n = max(n ,b);
    }

    bool find = false;
    for(i=0; i<=n; ++i)
        if(degree[i]%2 == 1){
            find = true;
            Eular(i);
            break;
        }

    if(!find)
        Eular(1);

    //output
    while(!ans.empty()){
        fout<<ans.top()<<endl;
        ans.pop();
    }
    return 0;
}
posted on 2011-01-02 21:30 小阮 阅读(336) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮