【2018寒假集训Day 8】【并查集】并查集模板

Luogu并查集模板题

#include<cstdio>

using namespace std;

int z,x,y,n,m,father[10001];

int getfather(int v)//找到根节点

{

    if (father[v]!=v) father[v]=getfather(father[v]);//路径压缩

    return father[v];

}

void hb(int x,int y)

{

    x=getfather(x);

    y=getfather(y);

    father[x]=y;//合并

}

bool check(int x,int y)

{

    x=getfather(x);

    y=getfather(y);

    if (x==y) return true;

    else return false;

}

int main()

{

    scanf("%d%d",&n,&m);

    for (int i=1;i<=n;i++)

        father[i]=i;

    for (int i=1;i<=m;i++)

    {

        scanf("%d%d%d",&z,&x,&y);

        if (z==1) hb(x,y);

        else if (check(x,y)) printf("Y\n");

        else printf("N\n");

    }

    return 0;

}

巴特西

【2018寒假集训Day 8】【并查集】并查集模板

最新文章

热门文章