图是否是树

yingl · yingl · commit b0b5646de49f · 2016-08-09T11:27:49.000+08:00
diff --git a/graph_valid_tree.py b/graph_valid_tree.py
@@ -0,0 +1,29 @@
+# -*- coding: utf-8 -*-
+
+class Solution:
+    # @param {int} n an integer
+    # @param {int[][]} edges a list of undirected edges
+    # @return {boolean} true if it's a valid tree, or false
+    def validTree(self, n, edges):
+        # Write your code here
+        # 如果是树，n个点有n - 1条边，遍历后包含所有点。
+        if len(edges) != (n - 1):
+            return False
+        # 重新构造无向树，[m, n] => t[m][n] = t[n][m] = True。
+        tree = [[False] * n for i in xrange(n)]
+        visited = [False] * n
+        for edge in edges:
+            tree[edge[0]][edge[1]] = True
+            tree[edge[1]][edge[0]] = True
+        # 从节点0开始深度遍历，这里顺便解决了输入为"1, []"的情况。
+        self.dfs(tree, visited, 0)
+        for i in xrange(n):
+            if not visited[i]:
+                return False
+        return True
+
+    def dfs(self, tree, visited, node):
+        visited[node] = True
+        for i in xrange(len(tree[node])):
+            if tree[node][i] and (not visited[i]):
+                self.dfs(tree, visited, i)
