Check whether given graph is valid tree bfs and dfs

lnk="https://www.lintcode.com/problem/178/"
from collections import deque,defaultdict as dd
class Solution:
    def validTree(self, n, edges):
        vis,g=set(),dd(list)
        for a,b in edges:
            g[a].append(b);g[b].append(a)
        def iscycle(x):
            q=deque()
            vis.add(x)
            q.append((x,-1))
            while q:
                v,p=q.popleft()
                for i in g[v]:
                    if i in vis and i!=p:
                        return True
                    elif i==p:continue
                    else:
                        vis.add(i)
                        q.append((i,v))
            return False
        cnt=0
        for i in range(n):
            if i not in vis:
                if iscycle(i):
                    return False
                cnt+=1
                if cnt>1:return False
        return True
DFS version
from collections import defaultdict as dd,deque
class Solution:
    def validTree(self, n, edges):
        g,vis=dd(list),set()
        for a,b in edges:g[a].append(b);g[b].append(a)
        def dfs(s,p):
            vis.add(s)
            for i in g[s]:
                if i==p:continue
                elif i in vis:return False
                else:
                    dfs(i,s)
            return True
        cnt=0
        for i in range(n):
            if i not in vis:
                if dfs(i,-1)==False:return False
                cnt+=1
                if cnt>1:return False
        return True