python--lintcode178. 判断图是否是树_python 判断一个图是否是树

所以思路明确了，就可以写代码了，请注意这一题只给了边的数组，所以我们需要自己来构建图的数据结构：

class Solution:
    """
    @param n: An integer
    @param edges: a list of undirected edges
    @return: true if it's a valid tree, or false
    """
    def validTree(self, n, edges):
        # write your code here
        if(n==1):return True
        if(len(edges)!=n-1):return False
        dic={}
        for i in range(n):
            dic[i]=set()  #集合里存储与该点连接的点
 
        def getGraph(dic,n,edges):   #获得图
            for i in range(len(edges)):
                u=edges[i][0]
                v=edges[i][1]
                dic[u].add(v)
                dic[v].add(u)
            return dic
 
        graph=getGraph(dic,n,edges)  #dic{i:set}
        from queue import  Queue
        q=Queue()
        q.put(0)
        traversal=set()   #记录已经遍历过的点
        while(q.qsize()!=0):
            node=q.get()
            for neighbor in graph[node]:
                if(neighbor in traversal):continue
                q.put(neighbor)
                traversal.add(neighbor)
 
        return(len(traversal)==n)
 
 
 
 
 
 
 
s = Solution()
print(s.validTree(5,[[0, 1], [0, 2], [0, 3], [1, 4]]))