Luogu

分析

并查集。

用数组$f[i][j]$来表示i和j是敌人,在每次输入敌人关系时循环合并即可。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
int root[1010]; //并查集 父节点 
bool f[1010][1010]; //仇敌关系  
int find(int x) //寻找根节点(有路径压缩) 
{
    if (root[x]!=x) root[x]=find(root[x]);
    return root[x];
}
void merge(int x,int y) //合并集合  
{
    int r1=find(x),r2=find(y);
    if (r1!=r2) root[r2]=r1;
}
int main()
{
    ios::sync_with_stdio(false); //加速cin & cout 
    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) root[i]=i; //初始化  
    while (m--)
    {
        char c; int a,b;
        cin>>c>>a>>b;
        if (c=='F') merge(a,b); //朋友就直接合并  
        else //仇敌关系  
        {
            f[a][b]=f[b][a]=true; //先保存  
            for (int k=1;k<=n;k++) //再循环合并  
            {
                if (f[a][k]) merge(b,k); //敌人的敌人是朋友  
                if (f[b][k]) merge(a,k); //同上  
            }
        }
    }
    int ans=0;
    for (int i=1;i<=n;i++) //统计父节点数(也就是团伙数) 
        if (root[i]==i) ans++;
    printf("%d\n",ans); //输出  
    return 0;
}
最后修改:2019 年 09 月 23 日 10 : 04 PM