Top

并查集


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
#include<stdlib.h>
#include <bits/stdc++.h>
#define fcin freopen("C:/Users/Administrator/Desktop/input.txt","r",stdin)
using namespace std;
const int maxn=2e5+7;
int Pre[maxn]; //上级数组
int Rank[maxn]; //数的高度

int Find(int x){ //查找上级
if(pre[x]==x){
return x;
}
return pre[x]=Find(pre[x]);

}
void Join(int x,int y){ //
int fx=Find(x),fy=Find(y);
if(fx==fy)return; //本是同源,无序替换
Pre[fy]=fx;
}
bool IsSame(int x,int y){ //检测连通性
if(Find(x)==Find(y))return true;
return false;
}
void Init(int n){ //初始化Pre,Rank
for(int i==0;i<=n;i++)Pre[i]=i,Rank[i]=1;
}
int main(){
fcin;
}

树层次优化Join

1
2
3
4
5
6
7
8
9
void Join(int x,int y){ //
int fx=Find(x),fy=Find(y);
if(fx==fy)return; //本是同源,无序替换
if(rank[fx]>rank[fy])pre[fy]=fx; //令y的上级的上级为x的上级
else{
if(rank[fx]==rank[fy])rank[fy]++;
pre[fx]=fy;
}
}
文章版权为Anoyer博客所有,转载请以链接形式标明本文地址