洛谷 P1892 [BOI2003]团伙

题目描述

1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：

我朋友的朋友是我的朋友；

我敌人的敌人也是我的朋友。

两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。

输入格式

输入文件gangs.in的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。第二行M(1<=M<=5000)，表示关于强盗的信息条数。以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。输入数据保证不会产生信息的矛盾。

输出格式

输出文件gangs.out只有一行，表示最大可能的团伙数。

输入输出样例

输入 #1复制

输出 #1复制

题解：

一道很好的并查集的题。

这道题的难点在于如何处理敌人的问题。

我们采用这样的方式：

建立一个e数组存放i的第一个敌人，如果之后还有敌人的话，就把这个敌人和e[i]合并即可。

这样的话这道题就非常简单了，我们注意一下统计的问题就可以。

但是我一开始WA了一个点，，就是因为我判的时候只判了e[p]没有判e[q]，两个都要判。

而且，要注意这里不能用scanf读字符，因为可能会有空格进入，不信你就试一试。

代码：

#include<cstdio>

#include<iostream>

using namespace std;

int n,m,ans;

int fa[1001],e[1001],v[1001];

int find(int x)

{

    if(fa[x]==x)

        return x;

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

}

void unionn(int x,int y)

{

    int fx=find(x);

    int fy=find(y);

    if(fx!=fy)

        fa[fx]=fy;

}

int main()

{

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

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

        fa[i]=i;

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

    {

        int p,q;

        char ch;

        cin>>ch>>p>>q;

        if(ch=='F')

            unionn(p,q);

        if(ch=='E')

        {

            if(!e[p])

                e[p]=q;

            else

                unionn(e[p],q);

            if(!e[q])

                e[q]=p;

            else

                unionn(e[q],p);

        }

    }

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

        v[find(i)]=1;

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

        if(v[i]==1)

            ans++;

    printf("%d",ans);

    return 0;

}

巴特西

BOI 2003 团伙

洛谷 P1892 [BOI2003]团伙

题目描述

输入格式

输出格式

输入输出样例

题解：

最新文章

热门文章