#P938. 道路建设
道路建设
描述 Description
Farmer John正在建设一组道路。这样他可以连接他的田地。有N块田地,P条道路。(n<=1000,p<=1000)
他需要你的帮助来确认他的设计:他必须保证能够从任意一块田地走到另外一块田地。
请设计一个程序帮助他来确认是否所有的田地都是相连的。
程序名:build
输入格式:
*第一行:两个由空格分隔的整数N和P。
*第2到P+1行: 每一行包含两个由空格分隔的整数,用来表示道路。
两个整数分别表示道路的起点和终点(两块田地)。道路可以从起点走到终点,也可以反向走动。田地的编号是从1到N。
样例输入:(文件名:build.in)
4 5
1 2
1 4
2 3
2 4
3 4
输出格式:
一行,输出能够由道路相连的田地的数目。(如果数目小于N,FJ可以知道他的设计有问题)
样例输出:(文件名:build.out)
4