261._Graph_Valid_Tree.md

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