首页 > 代码库 > poj1300判断欧拉回路

poj1300判断欧拉回路

2024-07-12 12:25:23   220人阅读

对于连通图

无向图：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;}


联系
我们