畅通工程Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 35088Accepted Submission(s): 18573
Problem Description
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
Input
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意:两个城市之间可以有多条道路相通,也就是说3 31 21 22 1这种输入也是合法的当N为0时，输入结束，该用例不被处理。
Output
对每个测试用例，在1行里输出最少还需要建设的道路数目。
Sample Input
4 21 34 33 31 21 32 35 21 23 5999 00
Sample Output
102998
因为是中文题目 就不翻译了
大概思路就是并查集根据给出的信息建立集合最后每两个相邻的点查找是否在一个集合中 不在则结果道路+1 并放入同一集合中最后输出结果
#include <iostream>#include <cstdio>using namespace std;const int maxn = 10000;int N, M;int pre[maxn];int ans;void join(int a, int b);int _find(int n);int main(){while(scanf("%d", &N)!=EOF && N){scanf("%d", &M);ans = 0;for(int i = 1; i <= N; ++i){//赋初值pre[i] = i;}for(int i = 1; i <= M; ++i){int a, b;scanf("%d%d", &a, &b);join(a, b);}for(int i = 1; i < N; ++i){if(_find(i) != _find(i+1)){//如果不在一个集合 则不存在畅通的道路++ans;//道路+1join(i, i+1);//两个点放入同一集合中}}printf("%d\n", ans);}return 0;}int _find(int n){//寻找根节点return pre[n] == n ? n : _find(pre[n]);}void join(int a, int b){//如果不在一个集合中 则加入此集合a = _find(a);b = _find(b);if(a != b){pre[a] = b;}}
人生就像一杯没有加糖的咖啡，喝起来是苦涩的，
