http://acm.hdu.edu.cn/showproblem.php?pid=1232
#include<iostream>
#include<set>
using namespace std;
struct Node
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int parent;
int hight;
};
Node village[1001];
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
int find(int x) //寻找父亲
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
while(x != village[x].parent)
x = village[x].parent;
return x;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
void merge(int a,int b)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(village[a].hight == village[b].hight)//树高一样
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
village[b].parent = a;
village[a].hight += 1;
}
else if(village[a].hight > village[b].hight) //矮树并入高树
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
village[b].parent = a;//并入a
}
else
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
village[a].parent = b;//并入b
}
}
int main()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int n;
while(scanf("%d",&n) && n)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int m,i,j,a,b,sum = 0;
for(i=1;i<=n;i++)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
village[i].parent = i;
village[i].hight = 1;
}
scanf("%d",&m);
while(m--)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
scanf("%d%d",&a,&b);
a = find(a); //寻找a的根节点
b = find(b); //寻找b的根节点
if(a!=b) //根节点不一样才合并
merge(a,b);
}
set<int>S;
for(i=1;i<=n;i++) //查找有多少个集合
S.insert(find(i));
cout<<S.size()-1<<endl;
}
return 0;
}
|