续并查集学习笔记——Gang团伙题解

一言不合先贴题目

Description

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足： 1、我朋友的朋友是我的朋友； 2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

Input

第1行为n和m，N小于1000,M小于5000；以下m行，每行为p x y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。

Output

一个整数，表示这n个人最多可能有几个团伙。

Sample Input

6
4
E 1 4
F 3 5
F 4 6
E 1 2

Sample Output

HINT

{1},{2,4,6},{3,5}

一开始的想法和ABC野兽那道题一样，可以维护每个点和祖先的关系。而且似乎更简单。于是有了下面的程序

#include<iostream>

#include<cstdio>

using namespace std;

int fa[],deep[],ans[][],n,m;

int getf(int k){

    if(fa[k]!=k){

        int t=fa[k];

        fa[k]=getf(fa[k]);

        deep[k]=deep[k]+deep[t];

        deep[k]=deep[k]%;

    }

    return fa[k];

}

int main(){

    cin>>n>>m;

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

        fa[i]=i;

        deep[i]=;

    }

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

        char c[];

        int x,y;

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

        if((c[]=='')&&(getf(x)!=getf(y))){

            int fx=getf(x);

            int fy=getf(y);

            deep[fx]=(deep[y]-deep[x]+)%;

            fa[fx]=fy;

        }

        if((c[]=='')&&(getf(x)!=getf(y))){

            int fx=getf(x);

            int fy=getf(y);

            deep[fx]=(deep[y]-deep[x]+)%;

            fa[fx]=fy;

        }

    }

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

        fa[i]=getf(i);

        //cout<<fa[i]<<" "<<deep[i]<<endl;

        ans[fa[i]][deep[i]]++;

    }

    int add=;

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

    for(int j=;j<=;++j)if(ans[i][j]>){

        add++;

    }

    cout<<add;

    return ;

}

然后、、、、、、就爆0了。

哪里出了问题？忽然发现题设中并没有：我的敌人的朋友是我的敌人。MDZZ！这不符合逻辑啊，虽然NOI从来不讲逻辑。

重新出发，想到分点的方法。通过朋友相关联的，fa[x]=y;通过敌人相关联的，fa[x]=y+n,fa[x+n]=y。该题完美解决。楼下程序：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int n,m,ans,a[];

int fa[];

int Find(int x)  {

    if(!fa[x]||fa[x]==x)

    return fa[x]=x;

    return fa[x]=Find(fa[x]);

    }

void Union(int x,int y)  {

    x=Find(x);y=Find(y);

    if(x==y) return ;

    fa[x]=y;

    }

int main(){

    int i,x,y;

    char p[];

    cin>>n>>m;

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

    {

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

        if(p[]=='F')

            Union(x,y);

        else

            Union(x,y+n),Union(x+n,y);

    }

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

        a[i]=Find(i);

    sort(a+,a+n+);

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

        if(i==||a[i]!=a[i-])

            ++ans;

    cout<<ans<<endl;

    return ;

}

To be continue......

秒客网