Skip to main content

Number of Connected Components in an Undirected Graph

Question​

None

Example 1
Input:  [[1,2], [2,3], [3,4], [5,6]]
Output: 4

Solution​

all//Number of Connected Components in an Undirected Graph.py


from collections import defaultdict

class Graph:
    def __init__(self,vertices):
        self.V=vertices
        self.graph=defaultdict(list)

    def addEdge(self,u,v):
        self.graph[u].append(v)
        self.graph[v].append(u)

    def connectedComponents(self):
        visited=[False]*self.V
        cc=0
        for i in range(self.V):
            if visited[i]==False:
                self.DFSUtil(i,visited)
                cc+=1
        return cc

    def DFSUtil(self,v,visited):
        visited[v]=True
        for i in self.graph[v]:
            if visited[i]==False:
                self.DFSUtil(i,visited)

g=Graph(5)
g.addEdge(1,0)
g.addEdge(2,3)
g.addEdge(3,4)

print("Number of connected components:",g.connectedComponents())