首页 > 代码库 > HDU - 1116 Play on Words

HDU - 1116 Play on Words

有向图是否具有欧拉通路或回路的判定:

欧拉通路:图连通;除2个端点外其余节点入度=出度;1个端点入度比出度大1;一个端点入度比出度小1 或 所有节点入度等于出度

欧拉回路:图连通;所有节点入度等于出度

#include<stdio.h>#include<string.h>#define MAX 27int in[MAX],out[MAX];int visit[MAX],father[MAX];int find(int index){    if(index==father[index]) return index;    else return find(father[index]);}int main(void){    int t,n;    int i,j;    int s,e;    char str[1001];    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        memset(visit,0,sizeof(visit));        memset(in,0,sizeof(in));        memset(out,0,sizeof(out));        for(i=0;i<MAX;i++) father[i]=i;        for(i=0;i<n;i++){            scanf("%s",str);            int len=strlen(str);            s=str[0]-a,e=str[len-1]-a;            father[s]=father[e]=find(s);            visit[s]=visit[e]=1;            out[s]++;in[e]++;        }        //判断改图是否连通        int r=0;        for(i=0;i<MAX;i++){            if(visit[i]&&i==father[i]) r++;        }        if(r>1){ //aba abc            printf("The door cannot be opened.\n"); continue;        }        int x,y,z,h;        x=y=z=h=0;        for(i=0;i<MAX;i++){            if(visit[i]){                if(out[i]-in[i]==1==1) x++;                else if(in[i]-out[i]==1)y++;                else if(in[i]==out[i]) z++;                else h++;            }        }        if(h==0&&((x==1&&y==1)||(x==0||y==0))) printf("Ordering is possible.\n");        else printf("The door cannot be opened.\n");    }    return 0;}