算法模板(四)并查集

并查集

#include<bits/stdc++.h>
#define maxn 3000
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n,m;
int fa[maxn];
inline void init(){
    for(register int i=0;i<=n;i++)fa[i]=i;
}
int get(int x){
    if(x==fa[x])return x;
    return get(fa[x]);
}
inline void merge(int x,int y){
    x=get(x);
    y=get(y);
    if(x!=y)fa[y]=x;
}
int a,b;
int main(){
    n=read();m=read();
    init();
    for(register int i=0;i<m;i++)merge(read(),read());
    return 0;
}

路径压缩并查集

#include<bits/stdc++.h>
#define maxn 3000
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
int n,m;
int fa[maxn];
inline void init(){
    for(register int i=0;i<=n;i++)fa[i]=i;
}
int get(int x){
    if(x==fa[x])return x;
    return fa[x]=get(fa[x]);
}
inline void merge(int x,int y){
    x=get(x);
    y=get(y);
    if(x!=y)fa[y]=x;
}
int a,b;
int main(){
    n=read();m=read();
    init();
    for(register int i=0;i<m;i++)merge(read(),read());
    return 0;
}