畅通工程 杭电oj1863 并查集实现

畅通工程 杭电oj1863 并查集实现

题目描述：
某省调查诚城镇交通情况，得到现有城镇道路统计表，表中列出了每条道路直接联通的城镇，省政府“畅通计划”的目标是使任意两个城镇之间都可以实现交通。（不一定市直达）问最少需要建设多少条路？
分析：
可以将每一个城镇看作是一个结点，将有路相连的城镇看作是一棵小树，问题的描述就可以转化为如何将所有的小树归并为一棵大树。
此处用到并查集的查找和合并功能:
查找：

int findx(int x)
{int i;int r=x;while(bin[r]!=r){r=bin[r];return r;}
}

将每个数组元素里面内容为自己的直属领导，这样子的话就可以一层一层查到老大；
合并：

int merge(int x,int y)
{	if(x!=y)//x,y分别为树的根节点，类似于老大；要想合并两个集合，只需要将两个老大进行统一即可{bin[x]=y;}
}

代码：

#include<stdio.h>
int bin[10000];
int findx(int x)//实现查找功能，找到某元素的老大
{int i;int r=x;while(bin[r]!=r){r=bin[r];return r;}
}
int merge(int x,int y)//实现合并功能，如果两个城镇之间有路，则合并成一个集合，一个做子节点，一个做根
{int fx,fy,t;fx=findx(x);fy=findx(y);if(fx!=fy){bin[x]=fy;}
}
int main()
{int n,m,i,x,y,count;while(scanf("%d",&n),n)//读入城镇个数{for(i=1;i<=n;i++){bin[i]=i;//起初假设每个都是老大，并没有路，每个集合都是一个数}for(scanf("%d",&m);m>0;m--)//提供几组有路的城市{scanf("%d %d",&x,&y);//读入有路的两个城镇merge(x,y);//合并城镇，将两个城镇合并为一个小树for(count=-1,i=1;i<=n;i++)//遍历数组中有几个老大，count为最少需要建立的路//做老大的条件：必须为bin[i]=i;其实老大就是根节点，初始化count是-1，//eg:如果有两个老大，只需要建立一条路{if(bin[i]==i)当老大的条件count++;}}printf("%dn",count);}return 0;
}