Update graph-valid-tree.cpp

kamyu104 · kamyu104 · commit af916e24dfde · 2015-10-25T12:11:50.000+08:00
diff --git a/C++/graph-valid-tree.cpp b/C++/graph-valid-tree.cpp
@@ -1,4 +1,3 @@
-
 // Time:  O(|V| + |E|)
 // Space: O(|V| + |E|)
 
@@ -33,6 +32,7 @@ class Solution {
             const int i = q.front();
             q.pop();
             visited.emplace(i);
+            --n;
             for (const auto& n : nodes[i].neighbors) {
                 if (n != nodes[i].parent) {
                     if (visited.find(n) != visited.end()) {
@@ -45,6 +45,6 @@ class Solution {
                 }
             }
         }
-        return true;
+        return n == 0;
     }
 };

Original file line number	Diff line number	Diff line change
`@@ -1,4 +1,3 @@`
`1`		`-`
`2`	`1`	`// Time: O(\|V\| + \|E\|)`
`3`	`2`	`// Space: O(\|V\| + \|E\|)`
`4`	`3`
`@@ -33,6 +32,7 @@ class Solution {`
`33`	`32`	`const int i = q.front();`
`34`	`33`	`q.pop();`
`35`	`34`	`visited.emplace(i);`
	`35`	`+ --n;`
`36`	`36`	`for (const auto& n : nodes[i].neighbors) {`
`37`	`37`	`if (n != nodes[i].parent) {`
`38`	`38`	`if (visited.find(n) != visited.end()) {`
`@@ -45,6 +45,6 @@ class Solution {`
`45`	`45`	`}`
`46`	`46`	`}`
`47`	`47`	`}`
`48`		`- return true;`
	`48`	`+ return n == 0;`
`49`	`49`	`}`
`50`	`50`	`};`