登录
← 返回首页 | 代码片段 › 2 数据结构 › 2.4 并查集 › 并查集 / 搜索
JSON MD

2.4 并查集

并查集 bcj
8 行
CPP JSON
【简单并查集(Union-Find)——数组实现 + 路径压缩】 ▪ find(int num) — 查找 num 的根节点,同时进行路径压缩(将节点直接指向根),使后续查找接近 O(1) ▪ fd[] 向量 — 存储每个节点的父节点,初始化 fd[i]=i 整体时间复杂度接近 O(α(N))(反阿克曼函数),近似常数。适用于连通性判断、集合合并等基础场景。
C++ 8 行 CPP
vector<int> fd(N, 0);
int find(int num) {
    if (fd[num] == num) {
        return num;
    } else {
        return fd[num] = find(fd[num]);
    }
}
并查集 dsu
45 行
CPP JSON
【并查集(DSU)类封装——路径压缩 + 按秩合并】 ▪ DSU(n) — 构造函数,初始化 n 个独立元素,parent[i]=i,rank[i]=0 ▪ init() — 重置所有元素为独立集合 ▪ find(x) — 查找 x 的根节点,同时路径压缩(递归将 parent[x] 设为根) ▪ unite(x, y) — 合并 x 和 y 所在集合,按秩合并(rank 小的合并到 rank 大的上,rank 相等时根 rank+1) ▪ isConnected(x, y) — 判断 x 和 y 是否在同一集合 均摊时间复杂度 O(α(N))。适用于 Kruskal 最小生成树、连通分量统计等。
C++ 45 行 CPP
class DSU {
private:
    vector<int> parent;
    vector<int> rank;
public:
    DSU(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }
    
    void init(){
        for (int i = 0; i < parent.size(); ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) return;
        
        if (rank[x] < rank[y]) {
            parent[x] = y;
        } else {
            parent[y] = x;
            if (rank[x] == rank[y]) {
                rank[x]++;
            }
        }
    }
    
    bool isConnected(int x, int y) {
        return find(x) == find(y);
    }
};
并查集 按秩合并 deep
28 行
CPP JSON
【并查集(按秩合并 deep)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void merge(Re x,Re y) — 合并操作 关键配置: N=1e4+3 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 27 行 CPP
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],deep[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
	x=find(x),y=find(y);
	if(x==y)return;
	if(deep[x]==deep[y])++deep[fa[x]=y];
	else if(deep[x]>deep[y])fa[y]=x;
	else fa[x]=y;
}
int main(){
	in(n),in(T);
	for(Re i=1;i<=n;++i)fa[i]=i;
	while(T--){
		in(op),in(x),in(y);
		if(op<2)merge(x,y);
		else puts(find(x)==find(y)?"Y":"N");
	}
}
并查集 按秩合并 size
28 行
CPP JSON
【并查集(按秩合并 size)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) void merge(Re x,Re y) — 合并操作 关键配置: N=1e4+3 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 27 行 CPP
#include<algorithm>
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N],size[N],deep[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:find(fa[x]);}
inline void merge(Re x,Re y){
	x=find(x),y=find(y);
	if(x==y)return;
	if(size[x]>size[y])std::swap(x,y);
	fa[x]=y,size[y]+=size[x];
}
int main(){
	in(n),in(T);
	for(Re i=1;i<=n;++i)fa[i]=i,size[i]=1;
	while(T--){
		in(op),in(x),in(y);
		if(op<2)merge(x,y);
		else puts(find(x)==find(y)?"Y":"N");
	}
}
并查集 路径压缩
21 行
CPP JSON
【并查集(路径压缩)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: void in(Re &x) — 核心算法函数 int find(Re x) — 查找(并查集寻根/二分查找) 关键配置: N=1e4+3 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 20 行 CPP
#include<cstdio>
#define Re register int
const int N=1e4+3;
int n,x,y,T,op,fa[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int find(Re x){return x==fa[x]?x:fa[x]=find(fa[x]);}
int main(){
	in(n),in(T);
	for(Re i=1;i<=n;++i)fa[i]=i;
	while(T--){
		in(op),in(x),in(y);
		if(op<2){if(find(x)!=find(y))fa[find(x)]=find(y);}
		else puts(find(x)==find(y)?"Y":"N");
	}
}
信息传递 并查集实战
38 行
CPP JSON
【信息传递(并查集实战)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: int min(int a,int b) — 核心算法函数 int find(int x) — 查找(并查集寻根/二分查找) void sakura(int a,int b) — 后缀数组 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 36 行 CPP
#include<cstdio>
#include<iostream> 
using namespace std;// 找图的最小环 
int minn=0x7fffff,n,f[200005],d[200005];
inline int min(int a,int b){if(a>b) return b;else return a;}

inline int find(int x){
	if(f[x]!=x){
		int l=f[x];
		f[x]=find(f[x]);
		d[x]+=d[l];
	}
	return f[x];
}

inline void sakura(int a,int b){
	int aa=find(a);int bb=find(b);
	if(aa!=bb){
		f[aa]=bb;
		d[a]=d[b]+1;
	}
	else
		minn=min(minn,d[a]+d[b]+1);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		sakura(i,x);
	}
	printf("%d",minn);
	return 0;
}

打击罪犯 并查集实战
65 行
CPP JSON
【打击罪犯(并查集实战)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: void add(int x,int y) — 加法更新 int find(int x) — 查找(并查集寻根/二分查找) void unionn(int r1,int r2) — 核心算法函数 void doit(无参数) — 核心算法函数 核心结构体:sakura 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 64 行 CPP
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int fa[1001],n,k;
struct sakura{int u,v,next;}sak[4001];
int st[1001],tot=0;
int p[1001],pp[1001];

void add(int x,int y){
    tot++;
    sak[tot].u=x;
    sak[tot].v=y;
    sak[tot].next=st[x];
    st[x]=tot;
}

int find(int x){
    if (fa[x]!=x)
       fa[x]=find(fa[x]);
    return fa[x];
}

void unionn(int r1,int r2){
    fa[r1]=r2;
}

void doit(){
    int i,j;
    for (i=n-1;i>=1;i--){
    	pp[i]=1;
        for (j=st[i];j;j=sak[j].next){
            if (pp[sak[j].v]){
               	int r1=find(sak[j].u);
               	int r2=find(sak[j].v);
               	if (r1!=r2){
                  	unionn(r1,r2);
                  	p[r1]+=p[r2]; 
                  	p[r2]=p[r1];
            	}
            }
        }
        if (p[find(i)]>(n+1)/2){
            printf("%d",i);
        }
    }
}

int main(){
    scanf("%d",&n);
    pp[n]=1;
    for (int i=1;i<=n;i++){
        scanf("%d",&k);
        fa[i]=i;
        p[i]=1; 
        for (int j=1;j<=k;j++){
            int x;
            scanf("%d",&x);
            add(i,x);
        }
    }
    doit();
    return 0;
}
格子游戏 二维并查集
27 行
CPP JSON
【格子游戏(二维并查集)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: T s(int x,int y) — 核心算法函数 核心结构体:T 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 26 行 CPP
#include<bits/stdc++.h>
using namespace std;
struct T{int x,y;}f[210][210];
int x,y,n,m;char c;T a1,a2;
T s(int x,int y){
    while((x==f[x][y].x)&&(y==f[x][y].y))return f[x][y];
    return s(f[x][y].x,f[x][y].y);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            f[i][j].x=i,f[i][j].y=j;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y>>c;
        if(c=='D')a1=s(x,y),a2=s(x+1,y);
        else a1=s(x,y),a2=s(x,y+1);
        if(a1.x==a2.x&&a1.y==a2.y){
            printf("%d\n",i);return 0;
        }
        else f[a2.x][a2.y]=a1;
    }
    printf("draw");
    return 0;
}
繁忙的都市 并查集+生成树
47 行
CPP JSON
【繁忙的都市(并查集+生成树)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: int find(int x) — 查找(并查集寻根/二分查找) bool cmp(const sakura &a,const sakura &b) — 核心算法函数 bool unions(int x,int y) — 核心算法函数 核心结构体:sakura 复杂度:均摊 O(α(N)),近似常数 说明:#include<bits/stdc++.h> 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 46 行 CPP
/*
            ���� 
           |   | 
           |   | 
           |   | 
      ������     ������ 
    |  ����ACʮ�ּ�   | 
     ������      ������ 
           |   | 
           |   | 
           |   | 
            ���� 
*/
//#include<bits/stdc++.h>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<algorithm>
int n,m,k,f[40001],sum;
struct sakura{
	int p,a,b,val;
}sak[40001];
inline int find(int x){return f[x]==x?x:find(f[x]);}
inline bool cmp(const sakura &a,const sakura &b){return a.val<b.val;}
inline bool unions(int x,int y){
	int fx=find(x),fy=find(y);
	if(fx==fy) return 0;
	else f[fy]=fx;
	return 1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) f[i]=i;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&sak[i].a,&sak[i].b,&sak[i].val);
	std::sort(sak+1,sak+1+m,cmp);
	for(int i=1;i<=m;i++){
		if(unions(sak[i].a,sak[i].b)){
			k++;
			sum=sak[i].val;
		}
		if(k==n-1) break;
	}
	printf("%d %d",n-1,sum);
	return 0;
} 
联络员 sort+并查集
27 行
CPP JSON
【联络员(sort+并查集)】 并查集(Disjoint Set Union)模板,支持集合合并与连通性查询。 核心函数: int fi(int x) — 核心算法函数 int cmp(const QAQ &a,const QAQ &b) — 核心算法函数 核心结构体:QAQ 复杂度:均摊 O(α(N)),近似常数 适用场景:连通分量统计、Kruskal MST、区间合并问题
C++ 26 行 CPP
#include<algorithm>
#include<cstdlib>
#include<cstdio>
int g,i,j,n,m,p,x,y,c,ans,k,f[2010];
struct QAQ{int l,r,w;}a[40010];
inline int fi(int x){if(x!=f[x])f[x]=fi(f[x]);return f[x];}
inline int cmp(const QAQ &a,const QAQ &b){return a.w<b.w;}
int main(){
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)f[i]=i;
    for(i=1;i<=m;i++){
        scanf("%d%d%d%d",&p,&x,&y,&c);
        if(p==1){ans+=c,f[fi(y)]=fi(x);}
        else a[++g].l=x,a[g].r=y,a[g].w=c;
    }
    std::sort(a+1,a+g+1,cmp);
    for(i=1;i<=g;i++){
        x=fi(a[i].l),y=fi(a[i].r);
        if(x!=y){
            f[y]=x;k++;
            ans+=a[i].w;
        }
    }
    printf("%d",ans);
    return 0;
}
已复制