张小花 @ 2019-08-22 20:54:41
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10010;
struct Node
{
int father, size;
};
Node trees[MAX_N];
int n, m;
int x, y, z, x_root, y_root;
int find_root(int index)
{
if (trees[index].father == -1)
{
return index;
}
int root = find_root(trees[index].father);
trees[index].father = root;
return root;
}
void merge(int root1, int root2)
{
if (trees[root1].size < trees[root2].size)
{
trees[root1].father = root2;
trees[root2].size += trees[root1].size;
}
else
{
trees[root2].father = root1;
trees[root1].size += trees[root2].size;
}
}
int main()
{
cin >> n >> m;
Node node;
node.size = 1;
node.father = -1;
for (int i = 1; i <= n; i++)
{
trees[i] = node;
}
for (int i = 1; i <= m; i++)
{
cin >> z >> x >> y;
x_root = find_root(x);
y_root = find_root(y);
if (z == 1)
{
merge(x_root, y_root);
}
else
{
if (x_root == y_root)
{
cout << "Y" << endl;
}
else
{
cout << "N" << endl;
}
}
}
return 0;
}
by 张小花 @ 2019-08-22 21:08:06
@Null_Cat 开了size就MLE是什么鬼 by the way 数据大不开size会TLE qwq
by longlongzhu123 @ 2019-08-22 21:10:29
@张小花 找到问题了:
问题出在 merge
函数里,数据有合并两个原本在同一集合里的元素的操作
修改后代码:
void merge(int root1, int root2)
{
if (root1 == root2) return;
if (trees[root1].size < trees[root2].size)
{
trees[root1].father = root2;
trees[root2].size += trees[root1].size;
}
else
{
trees[root2].father = root1;
trees[root1].size += trees[root2].size;
}
}
实测 AC
by 张小花 @ 2019-08-22 21:11:00
表示我用这个并查集A了 P1306
by longlongzhu123 @ 2019-08-22 21:11:09
MLE 应该是 find_root
会死循环,然后递归爆栈
by 张小花 @ 2019-08-22 21:11:40
@longlongzhu123 嗯哼 谢谢大佬
by Vomedakth @ 2019-08-22 21:11:59
@张小花
不加按秩合并不会影响太多时间复杂度,反正我没见过卡这个的
by 张小花 @ 2019-08-22 21:12:41
哦 突然发现我之前写了这句话。。 尴尬
by wkywkywky @ 2019-08-22 21:17:53
@张小花
merge(x_root, y_root);
可能把相同的两个元素合并起来,使
导致
if (trees[index].father == -1)
永远无法成立,爆栈了