Update graph-valid-tree.cpp

kamyu104 · kamyu104 · commit fe7ddfaab72b · 2015-10-25T12:36:16.000+08:00
diff --git a/C++/graph-valid-tree.cpp b/C++/graph-valid-tree.cpp
@@ -1,6 +1,7 @@
 // Time:  O(|V| + |E|)
 // Space: O(|V| + |E|)
 
+// Same complexity, but faster version.
 class Solution {
 public:
     struct node {
@@ -47,3 +48,42 @@ class Solution {
         return visited.size() == n;
     }
 };
+
+// Time:  O(|V| + |E|)
+// Space: O(|V| + |E|)
+class Solution2 {
+public:
+    struct node {
+        int parent = -1;
+        vector<int>neighbors;
+    };
+
+    bool validTree(int n, vector<pair<int, int>>& edges) {
+        unordered_map<int, node> nodes;
+        for (const auto& edge : edges) {
+            nodes[edge.first].neighbors.emplace_back(edge.second);
+            nodes[edge.second].neighbors.emplace_back(edge.first);
+        }
+
+        unordered_set<int> visited;
+        queue<int> q;
+        q.emplace(0);
+        while (!q.empty()) {
+            const int i = q.front();
+            q.pop();
+            visited.emplace(i);
+            for (const auto& node : nodes[i].neighbors) {
+                if (node != nodes[i].parent) {
+                    if (visited.find(node) != visited.end()) {
+                        return false;
+                    } else {
+                        visited.emplace(node);
+                        nodes[node].parent = i;
+                        q.emplace(node);
+                    }
+                }
+            }
+        }
+        return visited.size() == n;
+    }
+};
