dalao看看按秩合并哪个地方错了~不加按秩合并ac然而现在20分

P3367 【模板】并查集

张曜玺 @ 2017-10-29 21:27:04

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int father[10000],rank[10000];                                                                                                                                             
int find1(int x)//路径压缩递归版(易爆栈) 
{
    if(father[x]!=x) father[x]=find1(father[x]);
    return father[x];
}
int find2(int x)//路径压缩非递归版 
{
    int k,j,r=x;
    while(r!=father[r])
    r=father[r];
    k=x;
    while(r!=r)
    {
        j=father[k];
        k=j;
    }
    return r;
}
void un(int x,int y)//按秩合并 
{
    int r1=find2(x),r2=find2(y);
    if(r1==r2)return ;
    if(rank[x]<rank[y])//低的连到高的上 
    father[x]=y;
    else {
        father[y]=x;
        if(rank[x]==rank[y])rank[x]++;
    }
}
int main()
{
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++)
    father[i]=i;
    for (int i=1;i<=m;i++)
    {
        int bo,a,b;
        cin>>bo>>a>>b;
        if(bo==1)
        {
            un(a,b);
        }
        if(bo==2)
        {
            if(find2(a)==find2(b))
            {
                cout<<'Y'<<endl;
            }
            else{
            cout<<'N'<<endl; 
        }
    }
}

by VenusM1nT @ 2017-10-29 22:21:58

#include<cstdio>
int a,b,f[100005],n,m,p,c;
bool flag;
int find(int x)
{
    if(x!=f[x])
    {
        f[x]=find(f[x]);
        return f[x];
    }
    else return x;
}
int main()
{
    scanf("%d%d",&n,&p);
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=p;i++)
    {
        scanf("%d%d%d",&c,&a,&b);
        if(c==1) f[find(a)]=f[find(b)];
        else if(c==2)
        {
            if(find(a)==find(b)) printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}
这样就可以啊

by Uppk @ 2017-11-01 22:05:06

un函数中应该是把r1或r2的father改变再把作为祖先的那个father[r1/2]+=father[r2/1]吧


|