洛谷P2024 食物链 [NOI2001] 并查集

时间：2021-04-30 00:28:23

正解:并查集

解题报告:

传送门

这题，大概难点在分类讨论？（划

反正整个儿就并查集板子题了

说难点在分类讨论主要是因为,一般这种都是分成两组嘛,就很简单fa[x]=y fa[x+n]=y+n差不多这意思嘛

但是这个是分成三组,,,所以打起来就要注意一下理清条理,最好注释下什么东西是干什么的,这样打起来其实还是挺susi的(就像之前做这个一样(逃

没啦!代码放最后辣!over!

#include<bits/stdc++.h>

using namespace std;

#define ll long long

#define rp(i,x,y) for(register ll i=x;i<=y;++i)

#define lowbit(x) x&(-x)

const ll N=+;

ll n,k,fa[N*],ans;

inline ll read()

{

    register char ch=getchar();register ll x=;register bool y=;

    while(ch!='-' && (ch>'' || ch<''))ch=getchar();

    if(ch=='-')ch=getchar(),y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=getchar();

    return y?x:-x;

}

inline ll fd(ll x){return fa[x]==x?fa[x]:fa[x]=fd(fa[x]);}

int main()

{

    n=read();k=read();rp(i,,n*)fa[i]=i;

    rp(i,,k)

    {

        ll op=read();

        if(op==)

        {

            ll x=read(),y=read();

            if(x>n || y>n){++ans;continue;}

            ll fa1=fd(x),fa2=fd(y),fa3=fd(x+n),fa4=fd(y+n),fa5=fd(x+n+n),fa6=fd(y+n+n);

            if(fa3==fa2 || fa5==fa2){++ans;continue;}

            fa[fa1]=fa2;fa[fa3]=fa4;fa[fa5]=fa6;

            continue;

        }

        ll x=read(),y=read();

        if(x>n || y>n || x==y){++ans;continue;}

        ll fa1=fd(x),fa2=fd(y),fa3=fd(x+n),fa4=fd(y+n),fa5=fd(x+n+n),fa6=fd(y+n+n);

        if(fa1==fa2 || fa5==fa2){++ans;continue;}

        fa[fa3]=fa2;fa[fa6]=fa1;fa[fa5]=fa4;

    }

    printf("%lld\n",ans);

    return ;

}

//fax:xÒ»Àà fax+n:x³Ôʲô fax+2n:x±»³Ô

相关文章