Prerequisites: Graphs, DFS or BFS, Connected Components
Problem: Chef’s country has N cities, and M roads between them. The goal is to construct new roads so that there is a route between any two cities.
Find out the minimum number of roads required.
Solution Approach: The solution uses BFS(we can use DFS also) to find connected components in the graph. The number of connected components minus one represents the minimum number of roads needed to connect all cities. Why? Connecting any two cities within the same connected component requires only one road. Connecting C components requires C-1 roads because each road connects two components, and the last component doesn’t need an additional road.
Time complexity: O(N + M) as we need to explore all cities using BFS.
Space complexity: O(N) as we need to enqueue all nodes in a queue during bfs traversal.