graph_valid_tree.py

# -*- 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)