《Cracking the Coding Interview》——第4章:树和图——题目2
2024-08-31 03:31:13
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 ;
}
最新文章
- 锤子OneStep及BigBang使用体验
- Redis 学习(二)
- 排序算法 ----(转载::http://blog.csdn.net/hguisu/article/details/7776068)
- linux下使用rdp
- 小Experience__要懂得努力
- 【原创】试用十天被Pass所带来的启示
- brew命令
- PHP session 失效不传递的解决办法
- socket programming Max size of tcp/ip socket Buffer?
- CMOS Sensor的调试经验分享
- c++ 05
- 3.21	采购订单导入MDS
- Linux下tomcat管理查看控制台|杀死tomcat进程
- 【转载】The Elements of Programming Style之代码风格金科玉律
- SparkStreaming+Kafa+HBase
- Bootstrap 4 网格的基本结构
- [UWP]不那么好用的ContentDialog
- windows下配置pymysql
- Codeforces Round#412 Div.2
- 利用HTML5定位功能,实现在百度地图上定位(转)