2014-03-19 03:32

题目:给定一个有向图,判断其中两点是否联通。

解法:DFS搜索解决,如果是无向图的话,就可以用并查集高效解决问题了。

代码:

 // 4.2 Write a program to check if there exists a path between two nodes in a directed graph.
#include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#include <vector>
using namespace std; struct GraphNode {
int label;
unordered_set<GraphNode *> neighbors; GraphNode(int _label = ): label(_label) {};
}; bool hasPath(GraphNode *n1, GraphNode *n2, unordered_set<GraphNode *> &checked, vector<GraphNode *> &path)
{
if (n1 == nullptr || n2 == nullptr) {
return false;
} checked.insert(n1);
path.push_back(n1); if (n1 == n2) {
return true;
} unordered_set<GraphNode *>::iterator it;
for (it = n1->neighbors.begin(); it != n1->neighbors.end(); ++it) {
if (checked.find(*it) == checked.end()) {
if (hasPath(*it, n2, checked, path)) {
return true;
}
}
}
checked.erase(n1);
path.pop_back();
return false;
} void constructGraph(int n, vector<GraphNode *> &nodes)
{
int i;
int ne, x, y;
int label; nodes.resize(n);
for (i = ; i < n; ++i) {
scanf("%d", &label);
nodes[i] = new GraphNode(label);
} scanf("%d", &ne);
for (i = ; i < ne; ++i) {
scanf("%d%d", &x, &y);
nodes[x]->neighbors.insert(nodes[y]);
}
} void clearGraph(vector<GraphNode *> &nodes)
{
int n = (int)nodes.size();
int i; for (i = ; i < n; ++i) {
nodes[i]->neighbors.clear();
delete nodes[i];
nodes[i] = nullptr;
}
nodes.clear();
} int main()
{
int n;
vector<GraphNode *> nodes;
vector<GraphNode *> path;
unordered_set<GraphNode *> checked;
int idx1, idx2; while (scanf("%d", &n) == && n > ) {
constructGraph(n, nodes);
while (scanf("%d%d", &idx1, &idx2) == && (idx1 >= && idx2 >= )) {
if (idx1 >= n || idx2 >= n) {
continue;
} if (hasPath(nodes[idx1], nodes[idx2], checked, path)) {
printf("Yes\n");
printf("%d", path[]->label);
for (int i = ; i < (int)path.size(); ++i) {
printf("->%d", path[i]->label);
}
printf("\n");
} else {
printf("No\n");
}
checked.clear();
path.clear();
}
clearGraph(nodes);
} return ;
}

最新文章

  1. 锤子OneStep及BigBang使用体验
  2. Redis 学习(二)
  3. 排序算法 ----(转载::http://blog.csdn.net/hguisu/article/details/7776068)
  4. linux下使用rdp
  5. 小Experience__要懂得努力
  6. 【原创】试用十天被Pass所带来的启示
  7. brew命令
  8. PHP session 失效不传递的解决办法
  9. socket programming Max size of tcp/ip socket Buffer?
  10. CMOS Sensor的调试经验分享
  11. c++ 05
  12. 3.21 采购订单导入MDS
  13. Linux下tomcat管理查看控制台|杀死tomcat进程
  14. 【转载】The Elements of Programming Style之代码风格金科玉律
  15. SparkStreaming+Kafa+HBase
  16. Bootstrap 4 网格的基本结构
  17. [UWP]不那么好用的ContentDialog
  18. windows下配置pymysql
  19. Codeforces Round#412 Div.2
  20. 利用HTML5定位功能,实现在百度地图上定位(转)

热门文章

  1. myeclipse 10 创建webservice
  2. Last_SQL_Errno: 1050
  3. php图像处理插件imagick安装(仅适用于86位,php5.4非安全环境-16px)
  4. aop 和castle 的一些 学习文章
  5. 关于requireJS的同步加载和异步加载
  6. Android 最新学习资料收集
  7. (排班表二)后台动态绘制Grid表格
  8. Python简单线程间通信
  9. 爬虫学习(十四)——xpath项目实践
  10. javascript中string对象方法中的slice、substring、substr的区别联系