求助大佬

P3367 【模板】并查集

Clover_INF @ 2019-07-23 14:45:05

求助大佬，我的并查集不知为何只有40分，请大佬给我指点一下，谢谢

#include<cstdio>
#include<cstring>
using namespace std; 
int a[10001];

int find(int x)
{
    int k = x, p = x;
    while(a[k] > -1) {
        k = a[k];
    }
    while(a[p] > -1) {
        int temp = a[p];
        a[p] = k;
        p = temp;
    }
    return k;
}

void Union(int root1, int root2)
{
    int temp = a[root1] + a[root2];
    if(a[root2] < a[root1]) {
        a[root1] = root2;
        a[root2] = temp;
    }
    else {
        a[root2] = root1;
        a[root1] = temp;
    }
}

int main()
{
    int n, m;
    memset(a, -1, sizeof(a));
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int z, x, y;
        scanf("%d%d%d", &z, &x, &y);
        if(z == 1) Union(find(x), find(y));
        else {
            if(find(x) == find(y))    printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

by Lupus @ 2019-07-23 15:00:10

void Union(int root1, int root2)
{
    int temp = a[root1] + a[root2];
    if(a[root2] < a[root1]) {
        a[root1] = root2;
        a[root2] = temp;
    }
    else {
        a[root2] = root1;
        a[root1] = temp;
    }
}

冒昧的问一句，请问您为什么要新建一个节点呢？？

by Raw_Aya9285 @ 2019-07-23 15:03:42

@焦铭扬 主函数没问题 合并和查找的函数貌似都有问题

by Raw_Aya9285 @ 2019-07-23 15:04:34

诶不对 好像主函数也有问题

by Raw_Aya9285 @ 2019-07-23 15:12:05

@焦铭扬

find部分只用简单地判断：

if(a[x]!=x){  //如果祖先不是本身
    a[x]=find(a[x]);  //就继续找祖先
}
return a[x];  //返回祖先

这样就可以了。

为了配合这段函数，主函数的初始化应该是这样：

for(int i=1;i<=n;i++){
    a[i]=i;  //一开始每个人的祖先都是自己
}

另外合并函数内也只需要简单判断是否相同就可以了，大概如下：

int r1=find(root1),r2=find(root2);
if(r1!=r2){
    a[r2]=r1;
}

by Clover_INF @ 2019-07-23 15:19:39

@fishsause 我的并查集是每个的根节点存的是这个树元素的个数的复数，子节点存的是其父节点的下标，一开始每个人的祖先都是自己，所以都制成-1，而我第二个find函数是为了路径优化。我只过了4个，剩下的都是RE

|