为何这样写会MLE

低熵体 @ 2019-02-05 20:10:38

void merge(int x, int y)
{
    int fx, fy;
    fx = getf(x); fy = getf(y);
    //if (fx == fy) return;
    father[fy] = fx;
}

by WA鸭鸭 @ 2019-02-05 20:13:09

@dishangti 您确定不是并查集写错了？

by WA鸭鸭 @ 2019-02-05 20:13:19

@dishangti 查询函数

by 低熵体 @ 2019-02-05 20:21:53

@WA鸭鸭 应该不会吧我去掉就AC了

#include <iostream>

using namespace std;
int father[10010];
int n, m;

int getf(int x)
{
    if (father[x]) return father[x] = getf(father[x]);
    return x;
}

void merge(int x, int y)
{
    int fx, fy;
    fx = getf(x); fy = getf(y);
    if (fx == fy) return;
    father[fy] = fx;
}

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int z, x, y;
        cin >> z >> x >> y;
        if (z == 1) merge(x, y);
        else {
            if (getf(x) == getf(y)) cout << 'Y' << endl;
            else cout << 'N' << endl;
        }
    }
}

by 低熵体 @ 2019-02-05 20:25:33

@WA鸭鸭 哦哦知道了傻了，我试了不初始化自己为自己爹忘记了

by WA鸭鸭 @ 2019-02-05 20:27:50

@dishangti if (father[x])是啥qwq

by WA鸭鸭 @ 2019-02-05 20:28:11

@dishangti 我都是写的if(father[x]!=x)

by WA鸭鸭 @ 2019-02-05 20:28:26

@dishangti 没事，我也经常忘记初始化