qfpjm @ 2021-03-07 22:15:01
#include<bits/stdc++.h>
using namespace std;
const int len = 1000001;
int parent[len] = {0};
int n, m;
void union_(int v1, int v2){
int p1 = parent[v1];
int p2 = parent[v2];
if (p1 != p2)
{
for (int i = 0;i < len;i ++)
{
if (parent[i] == p1)
{
parent[i] = p2;
}
}
}
}
int find(int v1)
{
return parent[v1];
}
bool isSame(int v1, int v2)
{
return find(v1) == find(v2);
}
int main()
{
// 初始化, 所有的元素分别属于不同的集合
for (int i = 0; i < len; i++){
parent[i] = i;
}
cin >> n >> m;
for (int i = 1;i <= m;i ++)
{
int z, x, y;
scanf("%d%d%d", &z, &x, &y);
if (z == 1)
{
union_(x, y);
}
else
{
if (isSame(x, y))
{
printf("Y\n");
}
else
{
printf("N\n");
}
}
}
return 0;
}
by qfpjm @ 2021-03-07 22:16:02
by xfrvq @ 2021-03-07 22:18:04
神奇的写法
by xfrvq @ 2021-03-07 22:18:41
by xfrvq @ 2021-03-07 22:20:10
1e4再乘上1e5会爆
by CGDGAD @ 2021-03-07 22:20:27
union 这个写法太奇怪了,看一下题解吧
by CGDGAD @ 2021-03-07 22:22:05
void union_(int v1, int v2) {
int p1 = find(v1);
int p2 = find(v2);
if (p1 != p2)
{
f[v1] = p2;
}
}
感觉这个才对
by 可持久化CRTrie @ 2021-03-07 23:24:53
合并时更新的话应该和暴力差不多
by 可持久化CRTrie @ 2021-03-07 23:29:10
没有体现出并查集的优势