GUANLIN @ 2019-03-21 10:32:50
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<math.h>
#define LL long long
using namespace std;
const int N = 10001;
int n, m, head[N];
int findHead(int x)
{
if(head[x]<0) return x;
return head[x] = findHead(head[x]);
}
//void un(int x, int y)
//{
// int hx = findHead(x), hy = findHead(y);
// if(head[hx]<head[hy]) { head[hx]+=head[hy]; head[hy] = hx;}
// else {head[hy]+=head[hx]; head[hx] = hy;}
//}
//inline bool isUn(int x, int y)
//{
// return findHead(x)==findHead(y);
//}
int main()
{
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) head[i] = -1;
int x, y, z;
while(m--)
{
scanf("%d%d%d", &z, &x, &y);
if(z==1)
{
// un(x, y);
head[findHead(x)]=findHead(y);
}
else
{
if(findHead(x)==findHead(y)) printf("Y\n");
else printf("N\n");
}
}
return 0;
}
by 花里心爱 @ 2019-03-21 10:46:29
@GUANLIN qwq 初始化不应该是for(int i=1; i<=n; i++) head[i] = i;
吗
by GUANLIN @ 2019-03-21 10:48:59
@Irressey 我findHead里判断头结点的时候用的是if(head[x]<0) ... 应该和if(head[x]==x)是一个效果吧。
by GUANLIN @ 2019-03-21 10:52:40
...WTF?? 我改成```cpp head[i]=i;
```cpp
if(head[x]==x) return x;
就AC了??为什么..
by up_grant @ 2019-06-29 23:22:22
为什么这样判就会MLE啊,我就习惯用<0判
by 不穿靴子的猫 @ 2019-07-19 17:02:00
我也是欸,用-1就mle