Skip to content

261 Graph Valid Tree

261. Graph Valid Tree

题目: https://leetcode.com/problems/graph-valid-tree/

难度 : Medium

思路:

graph 为 tree 两个条件:

  • 这个图是connected
  • 没有cycle

偷懒AC代码,直接在323题,Number of Connected Components in an Undirected Graph上改的AC代码:

class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        def find(x):
            if uf[x] != x:
                uf[x] = find(uf[x])
            return uf[x]

        def union(x,y):
            xRoot = find(x)
            yRoot = find(y)
            uf[xRoot] = yRoot

        uf = [i for i in range(n)]

        for node1, node2 in edges:
            # cycle exists
            if find(node1) == find(node2):
                print 'ha '
                return False
            else:
                union(node1, node2)

        res = set()
        for i in range(n):
            res.add(find(i))

        return len(res) == 1


回到顶部