复兴提高DAY06并查集
2025-07-07 22:21:28
发布于:上海
T1【并查集】亲戚
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e3 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
int n, m, p;
cin >> n >> m >> p;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if (get(u) != get(v)) merge(u, v);
}
while (p--) {
int x, y;
cin >> x >> y;
if (get(x) == get(y)) cout << "Yes" << '\n';
else cout << "No" << '\n';
}
return 0;
}
T2【并查集】并查集
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
while (m--) {
int z, x, y;
cin >> z >> x >> y;
if (z == 1) {
if (get(x) != get(y)) merge(x, y);
}
else {
if (get(x) == get(y)) cout << "Y" << '\n';
else cout << "N" << '\n';
}
}
return 0;
}
T3【并查集】朋友圈的数量
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
if (get(u) != get(v)) merge(u, v);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i) ans++;
}
cout << ans << '\n';
return 0;
}
T4【并查集】村村通
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
int n;
while (cin >> n && n) {
for (int i = 1; i <= n; i++) fa[i] = i;
int m;
cin >> m;
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
if (get(x) != get(y)) merge(x, y);
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i) ans++;
}
cout << ans - 1 << '\n';
}
return 0;
}
T5【并查集】更好的沟通
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
int main() {
//图中的结点数是语言的数量+猫的数量 =1e5
//语言的下标改为 n+1 ~ n+m
int n, m;
cin >> n >> m;
for (int i = 1; i <= n + m; i++) fa[i] = i;
for (int i = 1; i <= n; i++) {
int k;
cin >> k;
while (k--) {
int x;
cin >> x;
if (get(x + n) != get(i)) { //第i个结点(猫)连上第x+n的结点(语言)
merge(x + n, i);
}
}
}
int num = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i) num++;
}
cout << num - 1;
return 0;
}
T6【并查集】团伙
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e3 + 9;
int fa[maxn];
int get(int x) {
if (fa[x] == x) return x;
return fa[x] = get(fa[x]);
}
void merge(int x, int y) {
fa[get(x)] = get(y);
}
vector<int> ve[maxn];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) fa[i] = i;
while (m--) {
char opt; int p, q;
cin >> opt >> p >> q;
if (opt == 'E') {
ve[p].push_back(q);
ve[q].push_back(p);
}
else {
if (get(p) != get(q)) merge(p, q);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j < ve[i].size(); j++) {
if (get(ve[i][j]) != get(ve[i][j - 1])) merge(ve[i][j], ve[i][j - 1]);
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (fa[i] == i) ans++;
}
cout << ans;
return 0;
}
这里空空如也
有帮助,赞一个