正文
《Cracking the Coding Interview》——第4章：树和图——题目2
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
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 ;
}
