10160 - Servicing Stations

一樣是要使用 backtrack 來 brute force

但重點在於如何減少遞回次數

本題用幾個方式來減少

1. 將整個 map 分成獨立的子map
    => 因為會可能出現互不相連的 map
          則考慮一個子map裡的city時，不用去檢查在其他獨立不相連子map中的city

2. 將相連的city 按照 index 順序從小到大排好
    => 這可以減少 backtrack 的遞回數
          例 : 相連的城市是 1 2 4 5
                 則當檢查到 4 時，發現 2 沒有被覆蓋且沒有serve station
                 而 4 之後的 city 也沒有和 2 相連            
                 則目前的解法就無法涵蓋 city，可以直接結束
                 而可以這樣做的原因是
                 backtrack 是按照排列過的順序一個一個檢查
                 如果檢查到4了，就代表2一定被檢查過
                 因此，2應該要被覆蓋，不然就是自己要有serve station

3. 當要給一個city設置serve station，則整體的 cover count 必須增加
    不然就不必考慮在此 city 設置 serve station 的情況

4. 在 backtrack 的期間，如果還沒做完就發現 station 數目比目前的 min還多
    就直接 return

用以上幾個減枝的方法，才有辦法在時間限制內做完

單純用backtrack，一定會 LTE

ref :
http://www.cnblogs.com/pangblog/p/3241212.html
http://mypaper.pchome.com.tw/zerojudge/post/1324488936 => 他說可以跑到0.012，有空研究一下
http://hi.baidu.com/zyz913614263/item/e6da83f0b2c57a1bc7dc4561 => 一些測資(這次沒用到)

#		Problem	Verdict	Language	Run Time	Submission Date
12263448	10160	Servicing Stations	Accepted	C++	0.222	2013-08-28 07:31:31

Time limit : 10.000 seconds

Problem D: Servicing stations

A company offers personal computers for sale in N towns (3 <= N <= 35). The towns are denoted by 1, 2, ..., N. There are direct routes connecting M pairs from among these towns. The company decides to build servicing stations in several towns, so that for any town X, there would be a station located either in X or in some immediately neighbouring town of X.
Write a program for finding out the minumum number of stations, which the company has to build, so that the above condition holds.
Input 
The input consists of more than one description of town (but totally, less than ten descriptions). Every description starts with number N of towns and number M of pairs of towns directly connected each other. The integers N and M are separated by a space. Every one of the next M rows contains a pair of connected towns, one pair per row. The pair consists of two integers for town's numbers, separated by a space. The input ends with N = 0 and M = 0.

Output
For every town in the input write a line containing the obtained minimum.

An example:

Input:
8 12
1 2
1 6
1 8
2 3
2 6
3 4
3 5
4 5
4 7
5 6
6 7
6 8
0 0
Output:
2