《Cracking the Coding Interview》——第4章：树和图—

《Cracking the Coding Interview》——第4章：树和图——题目2

2014-03-19 03:32

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

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

代码：

  1 // 4.2 Write a program to check if there exists a path between two nodes in a directed graph.
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <unordered_map>
  5 #include <unordered_set>
  6 #include <vector>
  7 using namespace std;
  8 
  9 struct  GraphNode {
 10     int label;
 11     unordered_set<GraphNode *> neighbors;
 12     
 13     GraphNode(int _label = 0): label(_label) {};
 14 };
 15 
 16 bool hasPath(GraphNode *n1, GraphNode *n2, unordered_set<GraphNode *> &checked, vector<GraphNode *> &path)
 17 {
 18     if (n1 == nullptr || n2 == nullptr) {
 19         return false;
 20     }
 21     
 22     checked.insert(n1);
 23     path.push_back(n1);
 24 
 25     if (n1 == n2) {
 26         return true;
 27     }
 28 
 29     unordered_set<GraphNode *>::iterator it;
 30     for (it = n1->neighbors.begin(); it != n1->neighbors.end(); ++it) {
 31         if (checked.find(*it) == checked.end()) {
 32             if (hasPath(*it, n2, checked, path)) {
 33                 return true;
 34             }
 35         }
 36     }
 37     checked.erase(n1);
 38     path.pop_back();
 39     return false;
 40 }
 41 
 42 void constructGraph(int n, vector<GraphNode *> &nodes)
 43 {
 44     int i;
 45     int ne, x, y;
 46     int label;
 47     
 48     nodes.resize(n);
 49     for (i = 0; i < n; ++i) {
 50         scanf("%d", &label);
 51         nodes[i] = new GraphNode(label);
 52     }
 53     
 54     scanf("%d", &ne);
 55     for (i = 0; i < ne; ++i) {
 56         scanf("%d%d", &x, &y);
 57         nodes[x]->neighbors.insert(nodes[y]);
 58     }
 59 }
 60 
 61 void clearGraph(vector<GraphNode *> &nodes)
 62 {
 63     int n = (int)nodes.size();
 64     int i;
 65     
 66     for (i = 0; i < n; ++i) {
 67         nodes[i]->neighbors.clear();
 68         delete nodes[i];
 69         nodes[i] = nullptr;
 70     }
 71     nodes.clear();
 72 }
 73 
 74 int main()
 75 {
 76     int n;
 77     vector<GraphNode *> nodes;
 78     vector<GraphNode *> path;
 79     unordered_set<GraphNode *> checked;
 80     int idx1, idx2;
 81     
 82     while (scanf("%d", &n) == 1 && n > 0) {
 83         constructGraph(n, nodes);
 84         while (scanf("%d%d", &idx1, &idx2) == 2 && (idx1 >= 0 && idx2 >= 0)) {
 85             if (idx1 >= n || idx2 >= n) {
 86                 continue;
 87             }
 88 
 89             if (hasPath(nodes[idx1], nodes[idx2], checked, path)) {
 90                 printf("Yes
");
 91                 printf("%d", path[0]->label);
 92                 for (int i = 1; i < (int)path.size(); ++i) {
 93                     printf("->%d", path[i]->label);
 94                 }
 95                 printf("
");
 96             } else {
 97                 printf("No
");
 98             }
 99             checked.clear();
100             path.clear();
101         }
102         clearGraph(nodes);
103     }
104     
105     return 0;
106 }