MaratonIME gets candies/Gym - 101375H/二分+交互
题目
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
题目来源：HDU 1232
题目链接
解法
n个城镇间能互相连通最少需要n-1条边，我们可以用并查集来找出已有的道路，然后用n-1再减去已有的道路即可得到答案。
代码：
#include <stdio.h>
#include <cstring>
#include <queue>
#include <math.h>
#include <algorithm>
using namespace std;
int fa[1010],n,m,x,y,l;int getfather(int x)
{if (fa[x]==x) return fa[x];fa[x]=getfather(fa[x]);return fa[x];
}int main()
{scanf("%d",&n);while (n!=0) {scanf("%d",&m);l=0;for (int i=1;i<=n;i++) fa[i]=i;for (int i=1;i<=m;i++) {scanf("%d%d",&x,&y);int fx=getfather(fa[x]);int fy=getfather(fa[y]);if (fx!=fy) {l++;fa[fy]=fx;}}printf("%d\n",n-1-l);scanf("%d",&n);} return 0;
}