并查集(递归写法)
#include<bits/stdc++.h>
using namespace std;
const int X = 10010;
int f[X];
int n, m;
//初始化
void init() {
for (int i = 0; i < X; i++) {
f[i] = i;
}
}
//查找上级是谁
int find(int x) {
if (x != f[x]) {
return f[x] = find(f[x]);//路径压缩
//相当于
/*
f[k]=find(f[k]);
return f[k];
*/
}
return f[x];
}
//合并
void join(int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
f[fy] = fx;
}
}
//判断集合个数
bool check()
{
int sum = 0;
for (int i = 1; i <= n; i++)
{
if (f[i] == i) sum++;//统计独立集合的个数
if (sum == 2) return 0;//发现有两个就返回false应该会省一点时间
}
return 1;//只有1个集合,返回true
}
int main() {
init();
cin >> n >> m;
while (m--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) {
join(x, y);
}
if (t == 2) {
if (find(x) == find(y))
cout << "Y" << endl;
else
cout << "N" << endl;
}
}
return 0;
}
并查集(循环写法)
#include<bits/stdc++.h>
using namespace std;
const int X = 10010;
int f[X];
int ceng[X];
int n, m;
//初始化
void init() {
for (int i = 0; i < X; i++) {
f[i] = i;
ceng[i] = 0;
}
}
//查找上级是谁
int find(int x) {
int i, j, k;
k = x;
while (k != f[k])
k = f[k];
i = x;
while (i != k) {
j = f[i];
f[i] = k;
i = j;
}
return k;
}
//合并
void join(int x, int y) {
int fx = find(x), fy = find(y);
if (ceng[fx] > ceng[fy])
f[fy] = fx;
else {
if (ceng[fx] == ceng[fy])
ceng[fy]++;
f[fx] = fy;
}
}
//判断集合个数
bool check()
{
int sum = 0;
for (int i = 1; i <= n; i++)
{
if (f[i] == i) sum++;//统计独立集合的个数
if (sum == 2) return 0;//发现有两个就返回false应该会省一点时间
}
return 1;//只有1个集合,返回true
}
int main() {
init();
cin >> n >> m;
while (m--) {
int t, x, y;
cin >> t >> x >> y;
if (t == 1) {
join(x, y);
}
if (t == 2) {
if (find(x) == find(y))
cout << "Y" << endl;
else
cout << "N" << endl;
}
}
return 0;
}
标签:int,fy,查集,ceng,fx,find
From: https://www.cnblogs.com/gaohaojie/p/18359615