MLE求助。。

P3367 【模板】并查集

GUANLIN @ 2019-03-21 10:32:50

几乎是照着题解模板改了..还是10个MLE .. 不知道为什么..

#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


|