訓練1　暢通工程

題目描述（HDU1232）：現有城鎮道路統計表，表中列出了每條直接相連的城鎮道路。“暢通工程”的目標是使全省任意兩個城鎮間都可以通過道路連接（間接通過道路連接也可以）。問最少還需要建設多少條道路？

輸入：輸入包含多個測試用例，每個測試用例的第1行都包含兩個正整數，分別是城鎮數量N（N<1000）和道路數量M；隨后的M行對應M條道路，每行都給出一對正整數，分別是該條道路連接的兩個城鎮的編號。城鎮編號為1～N。注意：兩個城市之間可以有多條道路相通。當N為0時，輸入結束。

輸出：對每個測試用例，都單行輸出最少還需要建設的道路數量。

題解：可以將一個連通分量看作一個集合，一條道路可以使兩個連通分量連通起來，相當于兩個集合的合并。因此只要統計道路網絡的連通分量數ans，再添加ans-1條道路即可。使用并查集可輕松解決。

1. 算法設計

（1）初始化。初始化每個節點的集合號為其自身。

（2）合并。每輸入一條邊的兩個端點x、y，都合并x、y的集合。

（3）統計并輸出結果。統計有多少個集合（集合號等于自身），每個集合都相當于一個連通分量，若有ans個集合，則添加ans-1條邊即可使其連通。最少還需要建設ans-1條道路。

2. 完美圖解

5個城鎮，兩條道路（1-2、3-5），一共3個集合，只需修建兩條道路即可。

3. 算法實現