nyoj99（并查集+欧拉路+dfs）

本文主要是介绍nyoj99（并查集+欧拉路+dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

单词拼接

描述

给你一些单词，请你判断能否把它们首尾串起来串成一串。

前一个单词的结尾应该与下一个单词的道字母相同。

如

aloha

dog

arachnid

gopher

tiger

rat

 

可以拼接成：aloha.arachnid.dog.gopher.rat.tiger

输入

第一行是一个整数N(0<N<20)，表示测试数据的组数
每组测试数据的第一行是一个整数M,表示该组测试数据中有M(2<M<1000)个互不相同的单词，随后的M行，每行是一个长度不超过30的单词,单词全部由小写字母组成。

输出

如果存在拼接方案，请输出所有拼接方案中字典序最小的方案。(两个单词之间输出一个英文句号".")
如果不存在拼接方案，则输出
***

样例输入

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

样例输出

aloha.arachnid.dog.gopher.rat.tiger
***

这题真心是好题，我做了整整2天终于给AC了，poj的题真心难！+_=

解题思路：

首先你必须将这道题建模成一个图，它只是第一个字母和最后一个字母接龙，所以只要用个结构体将他们单独取出，这是第一步，然后就需要判断这个图是不是连通图，

所以很自然想到并查集，但连通也会与很多种，也许有环，所以你又需要用欧拉路的定义来判断，当这些都满足了你只做到了第二步，这些字母可能会有重复的,

j就像这样（asdf,ajfhsdf)，没法你又要对图进行深度遍历，在遍历时将通路的所有字符转存到另外个数组str[1002][35]；这算是完了，但你要考虑输出的格式和这个字符数组中的值是什么序列的，所以建议自己单步调试下，这样你会更加明白！

代码如下（大部分函数都有注释）：

#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;char c[35],str[1002][35];
int number=0,pre[27],vis[27],cnt=0;
int in_du[27],out_du[27];
struct word1
{int star,end;int vis;//是否访问过char s[30];
}word[1002];bool cmp(word1 p, word1 q)
{return strcmp(p.s ,q.s)==-1; 
}//排序字符串的函数void serch(char *c)//初始化结构体数组函数
{int len=strlen(c);strcpy(word[number].s,c);word[number].vis=0;//初始该点未访问word[number].star=c[0]-'a'+1;out_du[c[0]-'a'+1]++;//出度自加word[number].end=c[len-1]-'a'+1;in_du[c[len-1]-'a'+1]++;//入度自加number++;
}int find1(int a)//并查集查找函数
{while(a!=pre[a])a=pre[a];return a;
}void join(int x,int y)//并查集连接函数
{x=find1(x);y=find1(y);if(x!=y)pre[x]=y;}void dfs(int x)//深度遍历
{for(int i=0;i<number;i++){if(!word[i].vis&&x==word[i].star){word[i].vis=1;//表示该点访问过dfs(word[i].end);//递归strcpy(str[cnt++],word[i].s);//将访问过的点都放如str数组中}}
}int main()
{int n,m,i;cin>>n;while(n--){bool flag=1;int flag1=0,flag2=0;cin>>m;if(m==0)flag=0;for(i=0;i<m;i++){cin>>c;serch(c);//输入在word结构体数组中}for(i=0;i<27;i++)//初始化并查集{pre[i]=i;vis[i]=0;//初始化访问数组}for(i=0;i<number;i++)//并查集实现{join(word[i].star,word[i].end);vis[word[i].end]=vis[word[i].star]=1;}int count =0;for(i=0;i<27&&flag;i++){if(vis[i]&&pre[i]==i)//查找根节点，若连通则count必为1count++;if(vis[i]&&in_du[i]!=out_du[i])//对每个点的入度和出度统计，判断是否存在有向图欧拉路{if(in_du[i]-out_du[i]==1)flag1++;else if (out_du[i]-in_du[i]==1)flag2++;else flag=0;}}if(count==1&&flag&&((flag1==0&&flag2==0)||(flag1==1&&flag2==1)) )//如果有向图连通且存在欧拉路{sort(word,word+number,cmp);	int start=word[0].star;for(i=0;i<27;i++){if(vis[i]&&out_du[i]==in_du[i]+1)//找到欧拉路的开始位置即出度比入度大1的点{start=i;break;}}dfs(start);//遍历图for(i=cnt-1;i>0;i--)cout<<str[i]<<'.';cout<<str[0];cout<<endl;}elsecout<<"***"<<endl;number=0;cnt=0;memset(in_du,0,sizeof(in_du));memset(out_du,0,sizeof(out_du));memset(vis,0,sizeof(vis));}return 0;
}

这篇关于nyoj99（并查集+欧拉路+dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---