BZOJ 1370: [Baltic2003]Gang团伙（luogu 1892）（种类并查集）

题面：

　　bzoj题面有误，还是看luogu的吧

　　https://www.luogu.org/problemnew/show/P1892

题解：

　　种类并查集。。

　　因为有敌人的敌人是朋友这个条件，所以需要一个中转点。。

　　因此，将每个点拆成两个点，一个是朋友点，另一个是敌人点。当读到A与B是朋友时，就将A与B所对应的朋友点并集；当读到两个点是敌人的时候，就将A点所对应的敌人点与B所对应的朋友点并集，将A所对应的朋友点和B所对应的敌人点并集。

　　P.S.当读到A与B点是朋友时，不能将A与B点所对应的敌人结点并集，因为题目并没有说朋友的敌人是敌人。

代码：

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

int fa[maxn],n,m,x,y,vis[maxn],ans;

char ch[];

int ffa(int x){

    return fa[x]==x?x:fa[x]=ffa(fa[x]);

}

int main(){

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

    for(int i=;i<=*n;i++) fa[i]=i;

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

        scanf("%s%d%d",ch,&x,&y);

        if(ch[]=='F'){

            int fx=ffa(x),fy=ffa(y);

            if(fx!=fy) fa[fy]=fx;

        }

        else{

            int fx=ffa(x),fy=ffa(y);

            int fxx=ffa(x+n),fyy=ffa(y+n);

            if(fx!=fyy) fa[fyy]=fx;

            if(fxx!=fy) fa[fxx]=fy;

        }

    }

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

        if(!vis[ffa(i)])

            ans++,vis[ffa(i)]=;

    printf("%d",ans);

    return ;

}

巴特西

BZOJ 1370: [Baltic2003]Gang团伙（luogu 1892）（种类并查集）

最新文章

热门文章