60 ms stack based and 64 ms DFS python


  • 0
    B
    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

  • 0
    B
    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)
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.