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
