class Solution(object):
def countComponents(self, n, edges):
"""
:type n: int
:type edges: List[List[int]]
:rtype: int
"""
retVal = 0
visited = [0]*n
stack = []
adjList = {x:[] for x in range(n)}
compList = [[]]
for x, y in edges:
adjList[x].append(y)
adjList[y].append(x)
for key in adjList:
if visited[key] == 1 :
continue
stack.append(key)
while(stack):
node = stack.pop()
if visited[node] == 1:
continue
visited[node] = 1
for x in adjList[node]:
if visited[x] == 1:
continue
stack.append(x)
retVal += 1
return retVal
60 ms stack based and 64 ms DFS python


class Solution(object): def countComponents(self, n, edges): """ :type n: int :type edges: List[List[int]] :rtype: int """ retVal = 0 self.visited = [0]*n self.adjList = {x:[] for x in range(n)} for x, y in edges: self.adjList[x].append(y) self.adjList[y].append(x) for n in self.adjList: if self.visited[n] == 1: continue self.dfs(n) retVal += 1 return retVal def dfs(self,node): if self.visited[node] == 1: return self.visited[node] = 1 for x in self.adjList[node]: if self.visited[x] != 1: self.dfs(x)