[Python] BFS, DFS. Count connected components
Problem reduces to number of connected components in undirected graph\n\n#### DFS\n\n\nimport collections\nclass Solution:\n    def dfs(self,node):\n        for
Problem reduces to number of connected components in undirected graph\n\n#### DFS\n\n```\nimport collections\nclass Solution:\n    def dfs(self,node):\n        for neighbor in self.graph[node]:\n            if neighbor not in self.seen:\n                self.seen.add(neighbor)\n                self.dfs(neighbor)\n\n\n    def makeConnected(self, n, connections):\n        num_cables=len(connections)\n        if num_cables<n-1:\n            return -1\n        self.graph = collections.defaultdict(list)\n        for i, j in connections:\n            self.graph[i].append(j)\n            self.graph[j].append(i)\n        num_connected_components=0\n        self.seen=set()\n        for node in range(n):\n            if node not in self.seen:\n                num_connected_components=num_connected_components+1\n                self.seen.add(node)\n                self.dfs(node)\n        return num_connected_components-1\n```\n\n#### BFS\n\n```\nimport collections\nclass Solution:\n    def bfs(self,node):\n        queue=collections.deque()\n        queue.append(node)\n        while(queue):\n            _node_=queue.popleft()\n            for neighbor in self.graph[_node_]:\n                if neighbor not in self.seen:\n                    queue.append(neighbor)\n                    self.seen.add(neighbor)\n\n\n    def makeConnected(self, n, connections):\n        num_cables=len(connections)\n        if num_cables<n-1:\n            return -1\n        self.graph = collections.defaultdict(list)\n        for i, j in connections:\n            self.graph[i].append(j)\n            self.graph[j].append(i)\n        num_connected_components=0\n        self.seen=set()\n        for node in range(n):\n            if node not in self.seen:\n                num_connected_components=num_connected_components+1\n                self.seen.add(node)\n                self.bfs(node)\n        return num_connected_components-1\n```
[]