并查集模板
int n,dad[N],sizee[N];//sizee数组规定只有祖宗结点是有效值
//初始化所有集合
void Init(){
for(int i=1;i<=n;i++){
dad[i]=i;
sizee[i]=1;
}
return ;
}
//查找a的祖宗节点
int Find(int a){
if(dad[a]!=a) dad[a]=Find(dad[a]);//每个集合中只有祖宗节点的值等于自身的值
return dad[a];
}
//将a和b的两个数所在的集合合并
void Merge(int a,int b){
if(Find(a)==Find(b)) return ;//特判a,b本身就在同一个集合之中
//先更新sizee数组再合并
sizee[Find(b)]+=sizee[Find(a)];
dad[Find(a)]=Find(b);
return ;
}
//判断a,b是否在同一个集合之中
bool Check(int a,int b){
if(Find(a)==Find(b)) return true;
else return false;
}
//统计a所在集合的元素个数
int Count(int a){
return sizee[Find(a)];
}AcWing 528. 奶酪
暴力+并查集:
#include<iostream>
#include<cmath>
using namespace std;
const int N=1e3+5;
int T,n,h,r,dad[N];
struct point{
int px,py,pz;
}p[N];
int find(int a){
if(dad[a]!=a) dad[a]=find(dad[a]);
return dad[a];
}
void merge(int a,int b){
if(find(a)==find(b)) return ;
else dad[find(a)]=find(b);
}
bool query(int a,int b){
if(find(a)==find(b)) return true;
else return false;
}
int main(){
cin>>T;
while(T--){
cin>>n>>h>>r;
for(int i=1;i<=n;i++){
cin>>p[i].px>>p[i].py>>p[i].pz;
dad[i]=i;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j){
double d=sqrt(pow(p[i].px-p[j].px,2)+pow(p[i].py-p[j].py,2)+pow(p[i].pz-p[j].pz,2));
if(d<=2*r){
merge(i,j);
}
}
}
}
int flag=0;
for(int i=1;i<=n;i++){
if(p[i].pz<=r){
for(int j=1;j<=n;j++){
if(p[j].pz>=h-r){
if(query(i,j)) {flag=1;break;}
}
}
}
}
if(flag==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
return 0;
}AcWing 836. 合并集合
#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,dad[N];
void init(){
for(int i=1;i<=n;i++) dad[i]=i;
return ;
}
int find(int a){
if(dad[a]!=a) dad[a]=find(dad[a]);
return dad[a];
}
void merge(int a,int b){
if(find(a)==find(b)) return ;
else dad[find(a)]=find(b);
return ;
}
void query(int a,int b){
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return ;
}
int main(){
cin>>n>>m;
init();
while(m--){
char ch;
int a,b;
cin>>ch>>a>>b;
if(ch=='M') merge(a,b);
else query(a,b);
}
return 0;
}AcWing 837. 连通块中点的数量
注意这里先改变集合的数量,再改变集合的祖宗
sizee[find(b)]+=sizee[find(a)];
dad[find(a)]=find(b);#include<iostream>
using namespace std;
const int N=1e5+5;
int n,m,dad[N],sizee[N];
void init(){
for(int i=1;i<=n;i++) dad[i]=i,sizee[i]=1;
return ;
}
int find(int a){
if(dad[a]!=a) dad[a]=find(dad[a]);
return dad[a];
}
void merge(int a,int b){
if(find(a)==find(b)) return ;
else{
//注意这里先改变集合的数量,再改变集合的祖宗
sizee[find(b)]+=sizee[find(a)];
dad[find(a)]=find(b);
return ;
}
}
void query(int a,int b){
if(find(a)==find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return ;
}
int count(int a){
return sizee[find(a)];
}
int main(){
cin>>n>>m;
init();
while(m--){
string s;
cin>>s;
if(s=="C"){
int a,b;
cin>>a>>b;
merge(a,b);
}
else if(s=="Q1"){
int a,b;
cin>>a>>b;
query(a,b);
}
else{
int a;
cin>>a;
cout<<count(a)<<endl;
}
}
return 0;
}AcWing 2069. 网络分析(第十一届省赛)
暴力+并查集(超时未AC 70points):
#include<iostream>
using namespace std;
const int N=1e4+5;
int n,m,dad[N],sizee[N];
void init(){
for(int i=1;i<=n;i++) dad[i]=i;
}
int find(int a){
if(dad[a]!=a) dad[a]=find(dad[a]);
return dad[a];
}
void merge(int a,int b){
if(find(a)==find(b)) return ;
else dad[find(a)]=find(b);
}
bool query(int a,int b){
if(find(a)==find(b)) return true;
else return false;
}
void count(int a,int t){
for(int i=1;i<=n;i++){
if(find(i)==find(a)){
sizee[i]+=t;
}
}
}
int main(){
cin>>n>>m;
init();
while(m--){
int x,y,z;
cin>>x>>y>>z;
if(x==1) merge(y,z);
else count(y,z);
}
for(int i=1;i<=n;i++) cout<<sizee[i]<<" ";
return 0;
}优化树上差分+并查集:
#include<iostream>
using namespace std;
const int N=1e4+5;
int n,m,dad[N],ans[N];
void init(){
for(int i=1;i<=n;i++) dad[i]=i;
}
int find(int a){
//路径压缩之后,父节点就是根节点
//因此两种情况直接返回:一个是根节点本身,另一个是节点和他的父结点
if(dad[a]==a||dad[dad[a]]==dad[a]) return dad[a];
int temp=find(dad[a]);
ans[a]+=ans[dad[a]];
dad[a]=temp;
return temp;
}
void merge(int a,int b){
if(find(a)==find(b)) return ;
else{
ans[find(a)]-=ans[find(b)];//保证a中的子树节点值不变
dad[find(a)]=find(b);
}
}
void count(int a,int t){
ans[find(a)]+=t;
}
int main(){
cin>>n>>m;
init();
while(m--){
int x,y,z;
cin>>x>>y>>z;
if(x==1) merge(y,z);
else count(y,z);
}
for(int i=1;i<=n;i++){
//根节点就直接输出权值
if(i==find(i)) cout<<ans[i]<<" ";
//每个节点的权值就等于该点的权值加上根节点的权值
else cout<<ans[i]+ans[find(i)]<<" ";
}
return 0;
}
