并查集:将编号分别为1到n的n个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。主要有两个操作:(1)合并两个集合,(2)查找某元素属于哪个集合。下面是利用并查集求解Hdu 1232 畅通工程(http://acm.hdu.edu.cn/showproblem.php?pid=1232),比用dfs,bfs搜索大大提高了时间效率。
#include <iostream>
#include <vector>
using namespace std;
vector <int> parents;
int findSet(int i)//if (parents[i]==i) then i is root;else if (parents[i]==j(j!=i)) then j is root.
{
int root=i;
while(root != parents[root]) //after loop get root
{
root=parents[root];
}
int k=i;
while(k != root) //path compression
{
int t=parents[k];
parents[k]=root;
k=t;
}
return root;
}
void unionSet(int a, int b)//union a,b to the small parent
{
int j=findSet(a);
int k=findSet(b);
if (j==k) return;
if (j<k)
{
parents[k]=j;
}
else
{
parents[j]=k;
}
}
bool run()
{
int n,m,i;
cin>>n;
if (n==0) return false;
cin>>m;
parents.resize(n+1);
for(i=1;i<=n;i++)
{
parents[i]=i; //init ,each i is a tree
}
for(i=0;i<m;i++)
{
int a,b;
cin>>a>>b;
unionSet(a,b);
}
int cntRoot=0;
for(i=1;i<=n;i++)
{
if (i==parents[i]) //count subtrees
{
cntRoot++;
}
}
cout << cntRoot-1 << endl;
return true;
}
int main()
{
while(run());
return 0;
}
说明:while(k != root) //把i开始结点的根修改为找到的根root,路径压缩便于提高效率
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
Hdu 3333解题报告 题意描述: 给你n个数现在要你求在k个区间上[ai, bi]的不相同的数之和各是多少. N,000; k,000; 显然,这题不能用暴力来做。 这题我们选择用线段数来做。
杭电OnlineJudge 200-2099的解题报告
解题报告|ACM|程序设计参考程序以及题目的分析
hdu1001解题报告
ACM程序设计题目分析以及AC的源码
100道 acm C语言 hdu 解题报告
HDU4802 GPA解题报告及一般代码的相关优化
HDU2501 Tiling_easy version 解题报告
hdu1290 解题报告 献给杭电五十周年校庆的礼物 (切西瓜问题,即平面分割空间)
90%的杭电母函数解题报告,有题目加解题思路,和ac掉的代码
算法-畅通工程(HDU-1232)(包含源程序).rar
题目链接题目意思有n个城镇,编号为0~n-1,m条道路,从一个城镇到另一个城镇有多条路,现在问你从一个城镇到另一个城镇的最短距离是多少。其中要注意的是,城镇之间
Least Common Multiple Problem Description The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set....
我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告。 里面包括题目、解题思路、编程技巧以及参考源码。所有代码都是使用C/C++写的。 最近整理资料时无意间发现,打包...
HDU解题报告,新手看看,高人也可以回顾下经典算法
ACM题库,一些题目和答案,以及解题报告,传上来共享
杭电ACM2000到2099一百道题的解题报告,全部是AC后的源码,不容错过
HDU2013暑期多校联合训练第一场0723-解题报告和标程