首页 > 代码库 > POJ 1386 单词接龙问题

POJ 1386 单词接龙问题

2024-07-20 06:47:41   222人阅读

题目大意：

给一堆字母，让它们进行接龙，要头对尾能够接的上，问有没有一种方法让所有成语都完成接龙

 

这道题实际上是在考虑是否存在一条欧拉通路，每个单词产生一条有向线段，由第一个字母指向最后一个字母

这道题另一个需要考虑的是是否所有存在的字母都是处于一个连通分量中的，这里我们考虑用并查集来解决问题。

 

代码如下：

 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int fa[30],in[30],out[30],visit[30]; 6 char str[1005]; 7 int find_head(int x) 8 { 9     int u=x;10     while(x!=fa[x]){11         x=fa[x];12     }13     fa[u]=x;14     return x;15 }16 int Union(int x,int y)17 {18     int fa_x=find_head(x);19     int fa_y=find_head(y);20     if(fa_x!=fa_y){21         fa[fa_x]=fa_y;22     }23     return fa_y;24 }25 int main()26 {27     int T,n,tmp;28     scanf("%d",&T);29     while(T--){30         scanf("%d",&n);31         memset(in,0,sizeof(in));32         memset(out,0,sizeof(out));33         memset(visit,0,sizeof(visit));34         for(int i=1;i<=26;i++) fa[i]=i;35         for(int i=0;i<n;i++){36             scanf("%s",str);37             int len=strlen(str);38             out[str[0]-‘a‘+1]++;39             in[str[len-1]-‘a‘+1]++;40             tmp=Union(str[0]-‘a‘+1,str[len-1]-‘a‘+1);//记录那个唯一的头结点41             //cout<<tmp<<endl;42             visit[str[0]-‘a‘+1]=1;43             visit[str[len-1]-‘a‘+1]=1;44         }45         bool flag=true;46         for(int i=1;i<=26;i++){47             if(visit[i]){48                 if(find_head(i)!=tmp){flag=false;break;}49             }50         }51         int cnt1=0,cnt2=0;52         for(int i=1;i<=26;i++){53             if(visit[i]){54                 if(in[i]-out[i]==1) cnt1++;55                 else if(out[i]-in[i]==1) cnt2++;56                 else if(in[i]!=out[i]) {flag=false;break;}57             }58         }59         if(!flag){60             printf("The door cannot be opened.\n");61             //continue;62         }63         else if((cnt1==1&&cnt2==1)||(cnt1==0&&cnt2==0)) puts("Ordering is possible.");64         else puts("The door cannot be opened.");65     }66     return 0;67 }

 

POJ 1386 单词接龙问题


联系
我们