并查集加训

2024-04-12 01:36

文章标签 查集加训

本文主要是介绍并查集加训，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.模板

在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int p[N];
int n, m;int fd(int x){if(x != p[x]){p[x] = fd(p[x]);}return p[x];
}int main(){scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){p[i] = i;}int z, x, y;while(m--){scanf("%d%d%d", &z, &x, &y);int xx = fd(x), yy = fd(y);if(z == 1){if(xx != yy){p[yy] = xx;} }else{if(xx == yy){cout<<"Y"<<endl;}else{cout<<"N"<<endl;}}}return 0;
}

2.亲戚（模板）

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int p[N];
int n, m, t;int fd(int x){if(x != p[x]){p[x] = fd(p[x]);}return p[x];
}int main(){cin>>n>>m>>t;for(int i = 1; i <= n; i++){p[i] = i;}int x, y;while(m--){cin>>x>>y;int xx = fd(x), yy = fd(y);if(xx != yy){p[yy] = xx;}}while(t--){cin>>x>>y;int xx = fd(x), yy = fd(y);if(xx != yy){cout<<"No"<<endl;	}else{cout<<"Yes"<<endl;}}return 0;
}

3.奶酪（维护连通球距离）

#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e3 + 10;
int p[N], a[N], b[N];
long long x[N], y[N], z[N];
int n, h;
long long r;long long dis(int i, int j){long long sum = 0;sum = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j]);return sum;
}int fd(int xx){if(xx != p[xx]){p[xx] = fd(p[xx]);}return p[xx];
}int main(){int t;cin>>t;while(t--){memset(p, 0, sizeof(p));cin>>n>>h>>r;for(int i = 1; i <= n; i++){p[i] = i;}int hh = 0, tt = 0;for(int i = 1; i <= n; i++){cin>>x[i]>>y[i]>>z[i];if(z[i] + r >= h){a[++hh] = i;}if(z[i] - r <= 0){b[++tt] = i;}for(int j = 1; j < i; j++){if(dis(i, j) <= 4 * r * r){int xx = fd(i), yy = fd(j);if(xx != yy){p[yy] = xx;}}}}int ok = 0;for(int i = 1; i <= hh; i++){if(ok) break;for(int j = 1; j <= tt; j++){if(fd(a[i]) == fd(b[j])){ok = 1;break;}}}if(ok) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0;
}

4.搭配购买（01背包）

可以选择多个集合的云，所以要用 01 背包
在这里插入图片描述

#include<iostream>
using namespace std;
const int N = 1e4 + 10;
int p[N];
int c[N], d[N], vv[N], ww[N], f[N];
int n, m, w;int fd(int x){if(x != p[x]){p[x] = fd(p[x]);}return p[x];
}int main(){cin>>n>>m>>w;for(int i = 1; i <= n; i++){p[i] = i;}for(int i = 1; i <= n; i++){cin>>c[i]>>d[i];}int u, v;for(int i = 1; i <= m; i++){cin>>u>>v;int xx = fd(u), yy = fd(v);if(xx != yy){p[yy] = xx;c[xx] += c[yy];d[xx] += d[yy];}}int cnt = 0;for(int i = 1; i <= n; i++){if(i == p[i]){vv[++cnt] = c[i];ww[cnt] = d[i];}}for(int i = 1; i <= cnt; i++){for(int j = w; j >= vv[i]; j--){f[j] = max(f[j], f[j - vv[i]] + ww[i]);}}cout<<f[w];return 0;
}

5.朋友（下标有负数用map）

分别求 -1 和 1 的朋友有多少个（包括他们自己），然后取最小的，就是对数
在这里插入图片描述

#include<iostream>
#include<map>
using namespace std;
const int N = 1e4 + 10;
map<int, int> p;
int n, m, t1, t2;int fd(int x){if(x != p[x]){p[x] = fd(p[x]);}return p[x];
}int main(){cin>>n>>m>>t1>>t2;for(int i = -m; i <= n; i++){p[i] = i;}int x, y;for(int i = 1; i <= t1 + t2; i++){cin>>x>>y;int xx = fd(x), yy = fd(y);if(xx != yy){p[yy] = xx;}}int res1 = 0, res2 = 0;for(int i = -m; i <= -1; i++){int xx = fd(-1), yy = fd(i);if(xx == yy){res1++;}}for(int i = 1; i <= n; i++){int xx = fd(1), yy = fd(i);if(xx == yy){res2++;}}int res = min(res1, res2);cout<<res;return 0;
}