4 21 34 33 31 21 32 35 21 23 5999 00Sample Output
102998          Huge input, scanf is recommended.Hint
                  Hint         {"safe":true,"sections":{"title":"","value":{"format":"HTML","content":"/u003cscript type/u003d/u0027text/x-mathjax-config/u0027/u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[/u0027$/u0027,/u0027$/u0027],[/u0027//[/u0027,/u0027//]/u0027]] } }); /u003c/script/u003e/n/u003cscript type/u003d/u0027text/javascript/u0027 src/u003d/u0027https://cdn.mathjax.org/mathjax/latest/MathJax.js?config/u003dTeX-AMS-MML_HTMLorMML/u0027/u003e/u003c/script/u003e/n/u003cscript type/u003d/u0027text/Javascript/u0027/u003esetTimeout(function(){MathJax.Hub.Queue([/u0027Typeset/u0027, MathJax.Hub, /u0027left_view/u0027]);}, 2000);/u003c/script/u003e/n/u003cdiv class/u003d/"panel_content/"/u003e/n  某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標是使全省任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設(shè)多少條道路？ /n /u003cbr/u003e /n/u003c/div/u003e"}},{"title":"Input","value":{"format":"HTML","content":"測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數(shù)，分別是城鎮(zhèn)數(shù)目N ( /u0026lt; 1000 )和道路數(shù)目M；隨后的M行對應(yīng)M條道路，每行給出一對正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號。為簡單起見，城鎮(zhèn)從1到N編號。 /n/u003cbr/u003e注意:兩個城市之間可以有多條道路相通,也就是說 /n/u003cbr/u003e3 3 /n/u003cbr/u003e1 2 /n/u003cbr/u003e1 2 /n/u003cbr/u003e2 1 /n/u003cbr/u003e這種輸入也是合法的 /n/u003cbr/u003e當N為0時，輸入結(jié)束，該用例不被處理。 /n/u003cbr/u003e"}},{"title":"Output","value":{"format":"HTML","content":"對每個測試用例，在1行里輸出最少還需要建設(shè)的道路數(shù)目。 /n/u003cbr/u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"/u003cPRe/u003e4 2/r/n1 3/r/n4 3/r/n3 3/r/n1 2/r/n1 3/r/n2 3/r/n5 2/r/n1 2/r/n3 5/r/n999 0/r/n0/u003c/pre/u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"/u003cpre/u003e1/r/n0/r/n2/r/n998/r/n/r/n/n        /n /u003ci style/u003d/"font-size:1px/"/u003e /u003c/i/u003e/r/nHuge input, scanf is recommended./u003c/pre/u003e"}},{"title":"Hint","value":{"format":"HTML","content":"/u003cpre/u003e/u003cdiv style/u003d/"font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px/"/u003e/n         /n  /u003cdiv style/u003d/"font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed/"/u003e /n    /n  /u003c/div/u003eHint/n        /n /u003c/div/u003e/u003c/pre/u003e"}}{"title":"","value":{"format":"HTML","content":"/u003cscript type/u003d/u0027text/x-mathjax-config/u0027/u003eMathJax.Hub.Config({tex2jax: { inlineMath: [[/u0027$/u0027,/u0027$/u0027],[/u0027//[/u0027,/u0027//]/u0027]] } }); /u003c/script/u003e/n/u003cscript type/u003d/u0027text/javascript/u0027 src/u003d/u0027https://cdn.mathjax.org/mathjax/latest/MathJax.js?config/u003dTeX-AMS-MML_HTMLorMML/u0027/u003e/u003c/script/u003e/n/u003cscript type/u003d/u0027text/javascript/u0027/u003esetTimeout(function(){MathJax.Hub.Queue([/u0027Typeset/u0027, MathJax.Hub, /u0027left_view/u0027]);}, 2000);/u003c/script/u003e/n/u003cdiv class/u003d/"panel_content/"/u003e/n  某省調(diào)查城鎮(zhèn)交通狀況，得到現(xiàn)有城鎮(zhèn)道路統(tǒng)計表，表中列出了每條道路直接連通的城鎮(zhèn)。省政府“暢通工程”的目標是使全省任何兩個城鎮(zhèn)間都可以實現(xiàn)交通（但不一定有直接的道路相連，只要互相間接通過道路可達即可）。問最少還需要建設(shè)多少條道路？ /n /u003cbr/u003e /n/u003c/div/u003e"}},{"title":"Input","value":{"format":"HTML","content":"測試輸入包含若干測試用例。每個測試用例的第1行給出兩個正整數(shù)，分別是城鎮(zhèn)數(shù)目N ( /u0026lt; 1000 )和道路數(shù)目M；隨后的M行對應(yīng)M條道路，每行給出一對正整數(shù)，分別是該條道路直接連通的兩個城鎮(zhèn)的編號。為簡單起見，城鎮(zhèn)從1到N編號。 /n/u003cbr/u003e注意:兩個城市之間可以有多條道路相通,也就是說 /n/u003cbr/u003e3 3 /n/u003cbr/u003e1 2 /n/u003cbr/u003e1 2 /n/u003cbr/u003e2 1 /n/u003cbr/u003e這種輸入也是合法的 /n/u003cbr/u003e當N為0時，輸入結(jié)束，該用例不被處理。 /n/u003cbr/u003e"}},{"title":"Output","value":{"format":"HTML","content":"對每個測試用例，在1行里輸出最少還需要建設(shè)的道路數(shù)目。 /n/u003cbr/u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"/u003cpre/u003e4 2/r/n1 3/r/n4 3/r/n3 3/r/n1 2/r/n1 3/r/n2 3/r/n5 2/r/n1 2/r/n3 5/r/n999 0/r/n0/u003c/pre/u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"/u003cpre/u003e1/r/n0/r/n2/r/n998/r/n/r/n/n        /n /u003ci style/u003d/"font-size:1px/"/u003e /u003c/i/u003e/r/nHuge input, scanf is recommended./u003c/pre/u003e"}},{"title":"Hint","value":{"format":"HTML","content":"/u003cpre/u003e/u003cdiv style/u003d/"font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px/"/u003e/n         /n  /u003cdiv style/u003d/"font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed/"/u003e /n    /n  /u003c/div/u003eHint/n        /n /u003c/div/u003e/u003c/pre/u003e"}}}
#include<stdio.h>#include<string.h>#include<math.h>#include<stdlib.h>#include<algorithm>#include<iostream>#include<queue>using namespace std;int city[1005];int already_road[1005];void  chu(){	for (int i = 1; i < 1001; i++)	{		city[i] = i;	}}int find(int x){	if(city[x]==x)	{		return x;	}	else	{		return city[x] = find(city[x]);	}}bool roadfind(int x){	for (int i = 0; already_road[i] != 0; i++)	{		if (already_road[i] == x)		{			return false;		}	}	return true;}int main(){	int num, roadnum;	while (cin >> num >> roadnum)	{		chu();		memset(already_road, 0, sizeof(already_road));		int s, e;		for (int i = 0; i < roadnum; i++)		{			cin >> s >> e;			city[find(s)] = city[find(e)];		}		//檢查有幾個集合		int k=0;		for (int i = 1; i <= num; i++)		{			int temp = find(city[i]);			if (roadfind(temp))			{				already_road[k++] = temp;			}		}		k -= 1;		cout << k<<'/n';	}	return 0;}//by swust_t_p