题解 P1892 【团伙】

· · 题解

//阅读题目一眼就能看出来这是个并查集的题

这个题的结点之间的关系是：

朋友的朋友是朋友，敌人的敌人是敌人

而且注意到：

输入数据保证不会产生信息的矛盾

所以连判定矛盾都不用了，就比较简单了

那么就可以把一个团伙当做一个并查集来看，直接在读入的同时合并所有的朋友关系，存下敌人关系，读入结束之后再合并所有的敌人的敌人

最后统计有多少个集合即可，用一个t数组来标记统计过的并查集的根节点，如果没有统计过一个并查集，答案数+1并标记该并查集的根结点

我不会说一开始以为敌人的朋友是敌人，朋友的敌人是敌人，做了好久

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <map>
#define For(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
bool t[1001];//et[1001][1001],t[1001];
short int n,m,fa[1001],e[1001][5001],ecnt[1001];
int find(int x)
{
    return fa[x]==x?x:(fa[x]=find(fa[x]));
}
void merge(int x,int y)
{
    fa[find(x)]=find(y);
}
int main()
{
    int tx,ty,ans=0;
    char temp;
    cin>>n>>m;
    For(i,1,n)
     fa[i]=i;
    For(i,1,m)
    {
        cin>>temp>>tx>>ty;
        if(temp=='E')
        {
            ecnt[tx]++;
            ecnt[ty]++;
            e[tx][ecnt[tx]]=ty;
            e[ty][ecnt[ty]]=tx;
            //et[tx][ty]=1;
            //et[ty][tx]=1;
        }
        else
        {
            merge(tx,ty);
        }
    }
    For(i,1,n)//处理敌人的敌人
    {
        For(j,1,ecnt[i])
        {
            tx=e[i][j];         //代码习惯不好，一开始写的很乱然后脑子短路这里就写错了- -
            For(h,1,ecnt[tx])
            {
                //if(!et[i][e[e[i][j]][h]])
                 merge(i,e[tx][h]);
            }
        }
    }
    For(i,1,n)//统计答案数
    {
        if(!t[find(i)])
        {
            ++ans;
            t[find(i)]=1;
        }
    }
    cout<<ans;
    return 0;
}