并查集一定要初始化自己为自己爹吗

P3367 【模板】并查集

低熵体 @ 2019-01-29 15:08:57

好像不初始化判断是否为0也可以啊?还是初始化会对其他题有什么帮助?

#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 _ctz @ 2019-01-29 15:13:23

说得好有道理


by pzc2004 @ 2019-01-29 15:15:14

初始化自己没有爹多没意思


by 源菌 @ 2019-01-29 15:16:51

@wemspzc ~烤绿鸟~


by 低熵体 @ 2019-01-29 17:37:58

@chino在我身下受 @wemspzc 定义为全局数组的话默认为0,初始化都免了。主要是我有时候会忘记初始化,想知道有没有影响


by Pbri @ 2019-03-21 12:53:49

没有问题,而且初始化为-1还可以做一些奇怪的事比如说求集合内的元素数量。。


by Ophelia @ 2019-07-14 07:46:23

@低熵体 并查集的本质是维护一个森林,把森林里的树合并。只要是达到这个目的都可以。但是初始化成自己的父节点的话会更容易理解并查集的本质。


|