Prerequisites: Graphs, DFS or BFS, Connected Components
Problem: In the vast galaxy, there are N planets connected by wormholes, forming a unique galactic network. Unfortunately, some planets are unreachable due to malfunctioning wormholes. To make all planets interconnected, scientists decided to place satellites in some planets and create inter-planet connections. The goal is to find the minimum number of satellites needed to connect all N planets.
Solution Approach: We can use DFS to find connected components in the graph. Each connected component represents a group of planets that can be connected with a single satellite. Basically we need at least one satellite in each connected group of planets so that it can connect with other groups of planets. Hence, total no. of connected groups of planets = minimum no. of satellite needed.
Time complexity: O(N + M) as we need to explore all planets using DFS.
Space complexity: O(N) as we need to store the visited states in an array.