浅谈并查集
并查集——树型数据结构，应用就是合并与查询
基本应用：初始化，查找祖先，合并以及判等
基础的并查集主要是板子，
初始化
点击查看代码
``` void renew（int n）{ for（int i=1;i<=n;i++){ f[i]=i;//因为此时没有信息所以自己就是自己根节点 } } ```点击查看代码
``` int find(int x){ if(f[x]!=x){ f[x]=find(f[x]);//f[x]表明是x的根节点记录 }//这里递归查找f【x】的父节点直至出现自己是自己父节点的根节点 return f[x];//实现一个路径压缩，方便下次查询 } ```点击查看代码
void unit(int x,int y){
int a=find(x);
int b=find(y);//寻找根节点
if(a!=b){
f[a]=b;//这部分视情况决定谁是根
}
}
点击查看代码
bool judge(int x,int y){
int a=find(x);
int b=find(y);
if(a==b){
return true;
}
else{
return false;
}
}
点击查看代码
#include
using namespace std;
const int a=52021;
int n,k;
int f[a],d[a];
int ans;
int find(int x){
if(f[x]!=x){
int t=f[x];
f[x]=find(f[x]);
d[x]=(d[x]+d[t])%3;
}
return f[x];
}
int main(){
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++){
f[i]=i;
d[i]=0;
}
int p,x,y;
for(int i=1;i<=k;i++){
scanf("%d%d%d",&p,&x,&y);
if(x>n||y>n||(p==2&&x==y)){
ans++;
continue;
}
int a=find(x);
int b=find(y);
if(p==1){
if(a==b){
if(d[x]!=d[y]){
ans++;
}
}
else{
f[a]=b;
d[a]=(d[y]-d[x]+3)%3;
}
}
else{
if(a==b){
if(d[x]!=(d[y]+1)%3){
ans++;
}
}
else{
f[a]=b;
d[a]=(d[y]-d[x]+4)%3;
}
}
}
cout< 点击查看代码
#include
#include
#include
#include
using namespace std;
const int MAXN=30005;
int read(){
int rv=0,fh=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
rv=(rv<<1)+(rv<<3)+c-'0';
c=getchar();
}
return rv*fh;
}
int fa[MAXN],dis[MAXN],t,num[MAXN];
int find(int x){
if(x!=fa[x]){
int k=fa[x];
fa[x]=find(fa[x]);
dis[x]+=dis[k];
num[x]=num[fa[x]];
}
return fa[x];
}
void merge(int x,int y){
int r1=find(x),r2=find(y);
if(r1!=r2){
fa[r1]=r2;dis[r1]=dis[r2]+num[r2];
num[r2]+=num[r1];
num[r1]=num[r2];
}
}
int query(int a,int b){
int r1=find(a),r2=find(b);
if(r1!=r2){
return -1;
}else {
return abs(dis[a]-dis[b])-1;
}
}
int main(){
t=read();
for(int i=1;i<=MAXN;i++) {fa[i]=i;num[i]=1;}
for(int i=1;i<=t;i++){
char c;
scanf(" %c ",&c);
int a=read(),b=read();
if(c=='M'){
merge(a,b);
}else {
printf("%d\n",query(a,b));
}
}
return 0;
}
点击查看代码
#include
using namespace std;
struct data{
int x;
int y;
int z;
}f[100005];
int n,m,a[20005],b[20005];
inline bool cmp(data a,data b){
return a.z>b.z;
}
inline int find(int x){
if(a[x]==x){
return x;
}
a[x]=find(a[x]);
return a[x];
}
inline void ad(int x,int y){
x=find(a[x]);
y=find(a[y]);
a[x]=y;
}
inline bool check(int x,int y){
x=find(x);
y=find(y);
if(x==y){
return true;
}
return false;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
a[i]=i;
}
for(int i=1;i<=m;i++){
scanf("%d%d%d",&f[i].x,&f[i].y,&f[i].z);
}
sort(f+1,f+m+1,cmp);
for(int i=1;i<=m+1;i++){
if(check(f[i].x,f[i].y)){
printf("%d",f[i].z);
break;
}
else{
if(!b[f[i].x]){
b[f[i].x]=f[i].y;
}
else{
ad(b[f[i].x],f[i].y);
}
if(!b[f[i].y]){
b[f[i].y]=f[i].x;
}
else{
ad(b[f[i].y],f[i].x);
}
}
}
return 0;
}