题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1269

思路分析:该问题要求判断是否每两个房间都可以相互到达,即求该有向图中的所有点是否只构成一个强连通图分量,使用Tarjan算法即可求解;

代码如下:

#include <stack>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std; const int MAX_N = + ;
vector<int> G[MAX_N];
stack<int> S;
int pre[MAX_N], lowlink[MAX_N], scc_no[MAX_N];
int dfs_clock, scc_cnt; inline int Min(int a, int b) { return a < b ? a : b; }
void Dfs(int u)
{
pre[u] = lowlink[u] = ++dfs_clock;
S.push(u); for (int i = ; i < G[u].size(); ++i)
{
int v = G[u][i]; if (!pre[v])
{
Dfs(v);
lowlink[u] = Min(lowlink[u], lowlink[v]);
} else if (!scc_no[v])
lowlink[u] = Min(lowlink[u], lowlink[v]);
}
if (lowlink[u] == pre[u])
{
scc_cnt++;
for (;;)
{
int x = S.top();
S.pop();
scc_no[x] = scc_cnt;
if (x == u) break;
}
}
} inline void FindScc(int n)
{
dfs_clock = scc_cnt = ;
memset(pre, , sizeof(pre));
memset(lowlink, , sizeof(lowlink));
memset(scc_no, , sizeof(scc_no));
for (int i = ; i <= n; ++i)
if (!pre[i]) Dfs(i);
} int main()
{
int ver_num, road_num; while (scanf("%d %d", &ver_num, &road_num) != EOF
&& (ver_num + road_num))
{
int ver_1, ver_2; for (int i = ; i < MAX_N; ++i)
G[i].clear( );
for (int i = ; i < road_num; ++i)
{
scanf("%d %d", &ver_1, &ver_2);
G[ver_1].push_back(ver_2);
}
FindScc(ver_num);
while (!S.empty( ))
S.pop( );
if (scc_cnt > )
printf("No\n");
else
printf("Yes\n");
}
return ;
}

最新文章

  1. JavaScript中正则表达式test()、exec()、match() 方法
  2. 如何优雅的在MFC中使用cvSetMouseCallback?
  3. zoj3745 Salary Increasing
  4. Asp.Net MVC3.0网站统计登录认证的在线人数
  5. 消除ComponentOne(C1StudioNet_2013v2) 的注册提示
  6. jquery layout学习
  7. BeanFactory not initialized or already closed - call &#39;refresh&#39; before access
  8. js父窗口opener与parent
  9. iOS开发 落地消息多的处理办法(仅供参考)
  10. QQ群成员提取
  11. mongoDB1--什么是mongoDB
  12. linux pci 协议一
  13. 关于阻止PROE联网的一些想法!
  14. 圆形border渐变加载
  15. 2015最新Android学习线路图
  16. vim的配置
  17. Spring Boot 静态页面
  18. java中一个Map要找到值Value最小的那个元素的方法
  19. web前端开发面试题(答案)
  20. mysql数据库存储引擎及区别

热门文章

  1. 【转】Java保留固定小数位的4种方法
  2. Oracle与SQL自治事务
  3. Jquery 获取IP地址
  4. ExtJS4.2学习(二)——入门基础
  5. iOS 开发技巧
  6. 修改IIS虚拟目录名称
  7. java的表达式
  8. Reorder the Books(规律)
  9. Android Animation动画(很详细)
  10. WCF 双工通信