普及-的并查集（都是板子）

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
struct Node{
int bn, ed, t;
}a[N];
int f[N];
int find(int x){ return x == f[x] ? x : f[x] = find(f[x]); }
bool cmp(Node x, Node y) { return x.t < y.t; }
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1;i <= m;i ++)
scanf("%d%d%d", &a[i].bn, &a[i].ed, &a[i].t);
sort(a + 1, a + m + 1, cmp);
for(int i = 0;i <= n;i ++) f[i] = i;
for(int i = 1;i <= m;i ++){
int fx = find(a[i].bn), fy = find(a[i].ed);
if(fx != fy)
f[fy] = fx, n --;
if(n == 1){
printf("%d", a[i].t);
return 0;
}
}
printf("-1");
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int _map[N][N], f[N];
struct Node{
int s, t, w;
}a[N * N];
bool cmp(Node x, Node y){ return x.w < y.w; }
int find(int x){ return f[x] == x ? x :f[x] = find(f[x]); }
int main(){
int n;
scanf("%d", &n);
int cnt = 0;
for(int i = 1;i <= n;i ++){
f[i] = i;
for(int j = 1;j <= n;j ++){
scanf("%d", &_map[i][j]);
if(i < j) a[++ cnt] = {i, j, _map[i][j]};
}
}
sort(a + 1, a + cnt + 1, cmp);
int ans = 0;
for(int i = 1;i <= cnt; i ++){
int fx = find(a[i].s), fy = find(a[i].t);
if(fx != fy){
f[fx] = fy;
ans += a[i].w;
n --;
}
if(n == 1){
printf("%d", ans);
return 0;
}
}
printf("-1");
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 7;
int f[N];
int st[N], t[N];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
int main(){
int n, m, p;
scanf("%d%d%d", &n, &m, &p);
for(int i = 0;i <= n;i ++) f[i] = i;
for(int i = 0;i < m;i ++) scanf("%d%d", &st[i], &t[i]);
for(int i = 0;i < m;i ++){
int fx = find(st[i]), fy = find(t[i]);
if(fx != fy)f[fx] = fy;
}
for(int i = 0;i < p;i ++){
int x, y;
scanf("%d%d", &x, &y);
if(find(x) == find(y))printf("Yes\n");
else printf("No\n");
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 2e4 + 7;
map<string, int> p;
int f[N];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
int main(){
string str;
int n, m, k;
cin >> n >> m;
for(int i = 1;i <= n;i ++){
cin >> str;
p[str] = i;
f[i] = i;
}
for(int i = 0;i < m;i ++){
string str1, str2;
cin >> str1 >> str2;
int fx = find(p[str1]), fy = find(p[str2]);
if(fx != fy) f[fx] = fy;
}
cin >> k;
for(int i = 0;i < k;i ++){
string str1, str2;
cin >> str1 >> str2;
int fx = find(p[str1]), fy = find(p[str2]);
if(fx == fy)printf("Yes.\n");
else printf("No.\n");
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7;
int f[N];
int find(int x){ return f[x] == x ? x : f[x] = find(f[x]); }
int main(){
int n, m;
cin >> n >> m;
for(int i = 0;i <= n;i ++) f[i] = i;
for(int i = 1;i <= m;i ++){
int p, x, y;
cin >> p >> x >> y;
if(p == 1){
int fx = find(x), fy = find(y);
if(fx != fy) f[fx] = fy;
}
else{
if(find(x) != find(y)) printf("N\n");
else printf("Y\n");
}
}
return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 7;
int f[N];
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
int main(){
int n, m, k;
cin >> n >> m >> k;
int ans = n * m;
for(int i = 0;i <= n * m;i ++)f[i] = i;
for(int i = 1;i <= k;i ++){
int x, y;
cin >> x >> y;
int fx = find(x), fy = find(y);
if(fx != fy){
f[fx] = fy;
ans --;
}
}
printf("%d", ans);
return 0;
}