Prerequisites: Graph Traversal Algorithms like DFS or BFS
Problem: Find the Number of Connected Components in an Undirected Graph
Solution Approach: This problem can be solved by either using DFS or BFS algorithm (DFS in our solution). The approach is to traverse the graph and mark the vertices belonging to each connected component. The algorithm iterates through all vertices, applying DFS to each unvisited vertex, and increments the count of connected components.
Time complexity: O(V + E) where V is no. of vertices and E is no. of edges. Mainly because we’re using DFS under the hood.
Space complexity: O(V) as we need an extra boolean array to store the visited/unvisited states of each vertices.