并查集&&最小生成树（模板）

小灰灰 2022-08-03 15:53 160阅读 0赞

并查集

int find(int x){				//查   查找根节点 
    	int r=x;
    	while(r!=pre[r])
    		r=pre[r];
    	int i=x,j;					//压缩路径 
    	while(i!=r){
    		j=pre[i];
    		pre[i]=r;
    		i=j;
    	}
    	return r;
    }
    void join(int x,int y){			//并 
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    		pre[fx]=fy;
    }

最小生成树（Kruskal算法     模板）

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    int pre[10000];
    int n;
    
    void init(){
    	for(int i=0;i<n;i++)
    		pre[i]=i; 
    }
    
    struct ak{
    	int s,c,l;
    }a[10000];
    
    int cmp(ak x,ak y){
    	return x.l<y.l;
    }
    
    int find(int x){				//查   查找根节点 
    	int r=x;
    	while(r!=pre[r])
    		r=pre[r];
    	int i=x,j;			//	-	
    	while(i!=r){			//	 |
    		j=pre[i];		//	 |
    		pre[i]=r;		//	 |-压缩路径 
    		i=j;			//	 |
    	}					//	-
    	return r;
    }
    
    void join(int x,int y){			//并 
    	int fx=find(x);
    	int fy=find(y);
    	if(fx!=fy)
    		pre[fx]=fy;
    }
    int main(){
    	while(...){
    		
    		... 
    		
    		init();
    		sort(a,a+n,cmp);
    		
    		... 
    		
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，160人围观）

还没有评论，来说两句吧...

相关阅读

相关最小生成树（并查集+Kruskal算法）

小生成树问题（MST）是为了解决以最低的花费连接所有的点（使图的连通分量的数目为1）而提出的。上**并查集+Kruskal算法**求解最小生成树问题的代码： ...

╰+哭是因爲堅強的太久メ/ 2024年04月17日 18:50/ 0 赞/ 64 阅读

相关最小生成树-Magicpig密室出逃(Kruskal+并查集)

文章目录 Kruskal算法题目分析代码小结 Kruskal算法 --------------------

秒速五厘米/ 2023年05月28日 11:12/ 0 赞/ 9 阅读

相关 HDU 1233(最小生成树,并查集)

这里使用kruskal: include <cstring> include <cstdio> include <queue> u

野性酷女/ 2022年09月20日 11:28/ 0 赞/ 152 阅读

相关 HDU 1232（最小生成树；并查集）

题意：如题。最小生成树建模方法：已有的边的花费为0，不存在的边花费为1，求最小生成树。 include<cstdio> include

淩亂°似流年/ 2022年09月20日 11:28/ 0 赞/ 178 阅读

相关并查集&&最小生成树（模板）

并查集 int find(int x){ //查查找根节点 int r=x; while(r!=pre[r]) r

小灰灰/ 2022年08月03日 15:53/ 0 赞/ 161 阅读

相关并查集 +最小生成树

并查集：并查集简单来说就是数据分类，怎么分呢，初始把数组 pre\[i\] = i 设定，表示自己归属于自己，如果A是B的老大，那么pre\[A\] = A， pre\

╰半夏微凉°/ 2022年06月10日 00:07/ 0 赞/ 208 阅读

相关 HDU-1863 畅通工程——并查集最小生成树Kruskal

畅通工程省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中

短命女/ 2022年06月07日 12:25/ 0 赞/ 186 阅读

相关连接的管道-HDU - 5253-并查集最小生成树

连接的管道老 Jack 有一片农田，以往几年都是靠天吃饭的。但是今年老天格外的不开眼，大旱。所以老 Jack 决定用管道将他的所有相邻的农田全部都串联起来，这样

红太狼/ 2022年06月06日 00:57/ 0 赞/ 186 阅读

相关温习Algs4 (五):并查集, 最小生成树

并查集, 带权图和最小生成树并查集 UnionFind.java 带权边和带权图 WeightedEdge.java

落日映苍穹つ/ 2022年04月11日 11:11/ 0 赞/ 198 阅读

相关并查集最小生成树复习

HDU 1856 more is better 简单并查集 ![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

一时失言乱红尘/ 2021年11月02日 14:24/ 0 赞/ 258 阅读