I have a python BFS solution however TLE with large test input


  • 0
    J
    class Solution(object):
    def countComponents(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: int
        """
        graph = {i:[] for i in range(n)}
        
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
        
        visited = [False]*n
        count = 0
        for i in range(n):
            if not visited[i]:
                count += 1
                queue = [i]
                while queue:
                    node = queue.pop(0)
                    visited[node] = True
                    for neigh in graph[node]:
                        queue.append(neigh)
                        if node in graph[neigh]:  # in case there is a cycle
                            graph[neigh].remove(node)
        return count

  • 2

    Hint: What is the runtime complexity of this line?

    graph[neigh].remove(node)
    

    I changed to the following and it got Accepted:

            while queue:
                node = queue.pop(0)
                if not visited[node]:
                    visited[node] = True
                    for neigh in graph[node]:
                        queue.append(neigh)

Log in to reply
 

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