题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1181
题意很简单。
有用并查集做的。我这里用传递闭包做。
有向图的传递闭包采用Floyd思想，可以判断任意两点之间是否有通路。
PS：Floyd思想：对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
这题代码：#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int map[200][200];
void floyd()
{
for(int i='a'; i<='z'; i++)
{
for(int j='a'; j<='z'; j++)
{
if(map[i][j]) //如果i->j
{
for(int k='a'; k<='z'; k++)
{
if(map[k][i]) //并且k->i
{
map[k][j] = 1; //那么k->j
}
}
}
}
}
}
int main()
{
char str[100];
memset(map,0,sizeof(map));
while(cin>>str)
{
if(strcmp(str,"0") == 0)
{
floyd();
if(map['b']['m'] == 1)
{
cout<<"Yes."<<endl;
}
else
{
cout<<"No."<<endl;
}
memset(map,0,sizeof(map));
}
else
{
int len = strlen(str);
map[str[0]][str[len-1]] = 1;
}
}
return 0;
}
自己犯的错误：
for(char i=’a’;i<=’z’;i++)
for(char j=’a’;j<=’z’;j++)
for(char k=’a’;k<=’z’;k++)
{
if(judge[adj[i]][adj[j]]==1&&judge[adj[j]][adj[k]]==1)
{
judge[adj[i]][adj[k]]=1;
}
}
结合Floyd做法来实现。（尽管DP原理偶还不是很懂。）
传递闭包自己写的，来一个错误例子 bg ga am….自己写这个显然可以找到反例。这个应该没问题。
另外数组下标是可以char类型的。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/110029.html原文链接：https://javaforall.net
