首页 > 其他 > 详细

poj1300判断欧拉回路

时间:2014-07-18 17:09:53      阅读:347      评论:0      收藏:0      [点我收藏+]

对于连通图

无向图:1.无奇点,可以从任意一点出发回到原点。 2.存在奇点,且只有两个,从一奇点出发,另一奇点终止。

有向图:1.所有点入度等于出度。 2.只有两个点入度不等于出度,且其中一个点入度比出度大一另一个点的出度比入度大一。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
using namespace std;
int s,n;
int ans[1000];
int ret;
void solve()
{
    char str[1000];
    for(int i=0;i<n;i++){
        cin.getline(str,100);
        int len=strlen(str);
        for(int j=0;j<len;j++){
            if(str[j]!= ){
                ans[i]++; ret++; int k=str[j]-0;ans[k]++;
            }
        }
    }
    cin.getline(str,100);
    int a=0;int b=0;
    for(int i=0;i<n;i++){
        if(ans[i]&1) a++;
        else b++;
    }
    if(a==0&&s==0)
    cout<<"YES "<<ret<<endl;
    else
        if(a==2&&s!=0&&ans[s]&1&&ans[0]&1)
        cout<<"YES "<<ret<<endl;
    else
        cout<<"NO"<<endl;
}
int main()
{
    char str[1000];char str1[1000];
    while(cin.getline(str,100)){
        ret=0;
        memset(ans,0,sizeof(ans));
        if(str[0]==S){
            sscanf(str,"%s%d%d",str1,&s,&n);
            solve();
        }
        else break;
    }
    return 0;
}

poj1300判断欧拉回路,布布扣,bubuko.com

poj1300判断欧拉回路

原文:http://www.cnblogs.com/yigexigua/p/3850900.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!