首页 > 代码库 > POJ 1386 单词接龙问题
POJ 1386 单词接龙问题
题目大意：
给一堆字母，让它们进行接龙，要头对尾能够接的上，问有没有一种方法让所有成语都完成接龙
这道题实际上是在考虑是否存在一条欧拉通路，每个单词产生一条有向线段，由第一个字母指向最后一个字母
这道题另一个需要考虑的是是否所有存在的字母都是处于一个连通分量中的，这里我们考虑用并查集来解决问题。
代码如下：
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 单词接龙问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。