HDU1181【有向图的传递闭包】

全栈程序员站长

发布于 2022-07-05 09:21:47

3730

发布于 2022-07-05 09:21:47

文章被收录于专栏：全栈程序员必看

题目链接：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.cn/110029.html原文链接：https://javaforall.cn

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2021年8月2，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法