Building Minimum warehouses A big international retailer is setting up shop in India and plans to open stores in N towns (3 ≤ N ≤ 1000), denoted by 1, 2, . . . , N. 
There are direct routes connecting M pairs among these towns. The company decides to build warehouses to ensure that for any town X, there will be a warehouse located either in X or in an immediately neighboring town of X.
I need to find the minimum number of warehouses the company has to build.
Example : If we have N=10 towns and 7 routes between :
1 2
2 4
2 5
3 6
8 6
9 7
10 7

Here answer will be 3.
Help me device an algorithm to do this problem.
 A: This problem is equivalent to finding the domination number of the graph, i.e., the smallest set $S$ of vertices such that every vertex of the graph lies in $S$ or its neighborhood $N(S)$.
Different graphs with the same $M$ (number of edges) may have different domination numbers.
I would thus try to find a domination number algorithm. The problem is NP hard, so it's not going to be fast for large graphs.
The brute force way to do this would be as follows.
Let $G$ be the graph whose vertices are towns, and whose edges are direct routes.
Run through every vertex set $S\subset V(G)$ of the graph from smallest to largest (so first check all single vertices, then all pairs, etc), and check if every vertex not in $S$ is adjacent to something in $S$ (so check if $V(G) \subseteq N(S)\cup S$).
As soon as you find a set $S$ that is adjacent to everything, stop the algorithm, and take the number of vertices in $S$ to be your answer.
It is important that you stop as soon as you find one, because this algorithm is already going to be painfully slow.
A: Use Algorithm to find the number of connected components in a graph. The number of components in the graph will show how many warehouses are needed.So, that every places is reachable.
