首页 > 代码库 > poj1386欧拉回路的判定

poj1386欧拉回路的判定

#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 father[1000];int getfather(int x){    if(x!=father[x]) father[x]=getfather(father[x]);    return father[x];}void add(int a,int b){    int fa=getfather(a);int fb=getfather(b);    if(fa!=fb) father[fa]=fb;}int vis[111111];int out[100],in[1000];bool ok(){    int one=0;int two=0;    int sum=0;    for(int i=0;i<26;i++)        if(vis[i]) if(father[i]==i) sum++;    if(sum>1) return false;    for(int i=0;i<26;i++){        if(in[i]-out[i]==1) one++;        if(out[i]-in[i]==1) two++;        if(out[i]==in[i]) continue;        if(out[i]-in[i]>1||in[i]-out[i]>1) return false;    }    return ((one==1&&two==1)||(one==0&&two==0));//  return one <= 1 && two <= 1}int main(){    int Icase;int n;    int G[100][100];    char str[2000];    cin>>Icase;    while(Icase--){        for(int i=0;i<26;i++) father[i]=i;        cin>>n;int ans=0;        memset(in,0,sizeof(in));        memset(out,0,sizeof(out));        memset(G,0,sizeof(G));        memset(vis,0,sizeof(vis));        for(int i=0;i<n;i++){            scanf("%s",str);int a=str[0]-a;int len=strlen(str);int b=str[len-1]-a;            add(a,b);in[b]++;out[a]++;vis[a]=1;vis[b]=1;        }        if(ok()) cout<<"Ordering is possible."<<endl;        else cout<<"The door cannot be opened."<<endl;    }    return 0;}