当前位置:首页 > 芯闻号 > 充电吧
[导读]并查集Union-Find Set或Disjoint Set(不相交集合),将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。常见的操作合并两个集合;将一元素并

并查集

Union-Find Set或Disjoint Set(不相交集合),将编号分别为1…N的N个对象划分为不相交集合,在每个集合中,选择其中某个元素代表所在集合。

常见的操作

合并两个集合;将一元素并入另一集体;判断两个元素是否属于同一个集合;每个集合用一棵“有根树”表示.

实现方法 每个集合用一棵“有根树”表示,定义数组 set[1..n],set[i] = i , 则i表示本集合,并是集合对应树的根,set[i] = j, j!=i, 则 j 是 i 的父节点.
树形结构,只需记录每个结点的父结点即可,每棵树表示一个集合,树的根作为集合的“代表元”。
对于查找操作,实际上沿着父指针,向上找到根即可
对于合并操作:只要把一个集合的根节点和另一个集合连接就可以了。
判断是否属于同一个集合的方法:由此用某个元素所在树的根结点表示该元素所在的集合,判断两个元素时候属于同一个集合的时候,只需要判断他们所在树的根结点是否一样
即可也就是说,当我们合并两个集合的时候,只需要在两个根结点之间连边即可

HDOJ 1232 Problem Description
某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路?
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M;随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号。为简单起见,城镇从1到N编号。
注意:两个城市之间可以有多条道路相通,也就是说  3 3    1 2    1 2    2 1   这种输入也是合法的
当N为0时,输入结束,该用例不被处理。 对每个测试用例,在1行里输出最少还需要建设的道路数目。
地图上若干城镇都可以看作点,已知哪些对城镇之间是有道路直接相连的。最后要解决的是整幅图的连通性问题,即求整幅图一共有几个连通分支,也就是被分成了几个互相独立的块。 畅通工程这题,问还需要修几条路,实质就是求有几个连通分支。如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了;如果是2个连通分支,则只要再修1条路,从两个分支中各选一个点,把它们连起来,那么所有的点都是连起来的了;如果是n个连通分支,则只要再修n-1条路。

#include#define M 1000
int F[M];//并查集的根节点保存的数组
void Init(int *F)//初始化
{
    int i=0;
    for(i=0;i<M;i++)
        F[i]=i;
}
int find(int x)//查找元素所在的集合
{
    while(F[x]!=x)
    {
       x=F[x];
    }
    return x;
}
void Union(int u, int v)
{
	int s1 = find(u), s2 = find(v);
	if (s1 != s2) F[s1] = s2;
}
int main()
{
    int n,m;//城镇数目n和道路数目m
    int m_a,m_b;//m行测试数据的对应的两个数据,表示城镇ma和mb之间联通
    int i,count=0;
    freopen("input.txt","r",stdin);
    while(scanf("%d %d",&n,&m))
    {
        count=0;
        if(n==0)
        break;
        Init(F);
        while(m--)
        {
            scanf("%d %d",&m_a,&m_b);//把两个节点结合起来
            Union(m_a,m_b);
        }
        for(i=1;i<=n;i++)
        {
            if(F[i]==i)
            {
                count++;
            }
        }
        printf("%dn",count-1);//因为如果全部连接起来的话,根节点的还是会有i还是满足i=F[i]的。
    }
}


优化——路径压缩
思想:每次查找的时候,如果路径较长,则修改信息,以便下次查找的时候速度更快。
第一步,找到根结点 第二步,修改查找路径上的所有节点,将它们都指向根结点



带路径压缩的查找算法

int find(int x)
{
    int k, j, r;
    r = x;
    while(r != parent[r])     //查找跟节点
        r = parent[r];      //找到跟节点,用r记录下
    k = x;        
    while(k != r)             //非递归路径压缩操作
    {
        j = parent[k];         //用j暂存parent[k]的父节点
        parent[k] = r;        //parent[x]指向跟节点
        k = j;                    //k移到父节点
    }
    return r;         //返回根节点的值            
}


int find(int x)       //查找x元素所在的集合,回溯时压缩路径
{
    if (x != parent[x])
    {
        parent[x] = find(parent[x]);     //回溯时的压缩路径
    }         //从x结点搜索到祖先结点所经过的结点都指向该祖先结点
    return parent[x];
}
//采用递归的方式压缩路径, 但是,递归压缩路径可能会造成溢出栈










本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

9月2日消息,不造车的华为或将催生出更大的独角兽公司,随着阿维塔和赛力斯的入局,华为引望愈发显得引人瞩目。

关键字: 阿维塔 塞力斯 华为

加利福尼亚州圣克拉拉县2024年8月30日 /美通社/ -- 数字化转型技术解决方案公司Trianz今天宣布,该公司与Amazon Web Services (AWS)签订了...

关键字: AWS AN BSP 数字化

伦敦2024年8月29日 /美通社/ -- 英国汽车技术公司SODA.Auto推出其旗舰产品SODA V,这是全球首款涵盖汽车工程师从创意到认证的所有需求的工具,可用于创建软件定义汽车。 SODA V工具的开发耗时1.5...

关键字: 汽车 人工智能 智能驱动 BSP

北京2024年8月28日 /美通社/ -- 越来越多用户希望企业业务能7×24不间断运行,同时企业却面临越来越多业务中断的风险,如企业系统复杂性的增加,频繁的功能更新和发布等。如何确保业务连续性,提升韧性,成...

关键字: 亚马逊 解密 控制平面 BSP

8月30日消息,据媒体报道,腾讯和网易近期正在缩减他们对日本游戏市场的投资。

关键字: 腾讯 编码器 CPU

8月28日消息,今天上午,2024中国国际大数据产业博览会开幕式在贵阳举行,华为董事、质量流程IT总裁陶景文发表了演讲。

关键字: 华为 12nm EDA 半导体

8月28日消息,在2024中国国际大数据产业博览会上,华为常务董事、华为云CEO张平安发表演讲称,数字世界的话语权最终是由生态的繁荣决定的。

关键字: 华为 12nm 手机 卫星通信

要点: 有效应对环境变化,经营业绩稳中有升 落实提质增效举措,毛利润率延续升势 战略布局成效显著,战新业务引领增长 以科技创新为引领,提升企业核心竞争力 坚持高质量发展策略,塑强核心竞争优势...

关键字: 通信 BSP 电信运营商 数字经济

北京2024年8月27日 /美通社/ -- 8月21日,由中央广播电视总台与中国电影电视技术学会联合牵头组建的NVI技术创新联盟在BIRTV2024超高清全产业链发展研讨会上宣布正式成立。 活动现场 NVI技术创新联...

关键字: VI 传输协议 音频 BSP

北京2024年8月27日 /美通社/ -- 在8月23日举办的2024年长三角生态绿色一体化发展示范区联合招商会上,软通动力信息技术(集团)股份有限公司(以下简称"软通动力")与长三角投资(上海)有限...

关键字: BSP 信息技术
关闭
关闭