畅通工程 并查集

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  某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ /n /u003cbr/u003e /n/u003c/div/u003e"}},{"title":"Input","value":{"format":"HTML","content":"测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( /u0026lt; 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从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时，输入结束，该用例不被处理。 /n/u003cbr/u003e"}},{"title":"Output","value":{"format":"HTML","content":"对每个测试用例，在1行里输出最少还需要建设的道路数目。 /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  某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？ /n /u003cbr/u003e /n/u003c/div/u003e"}},{"title":"Input","value":{"format":"HTML","content":"测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( /u0026lt; 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从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时，输入结束，该用例不被处理。 /n/u003cbr/u003e"}},{"title":"Output","value":{"format":"HTML","content":"对每个测试用例，在1行里输出最少还需要建设的道路数目。 /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