题目描述

• 我的朋友的朋友是我的朋友。
• 我的敌人的敌人是我的朋友。
• 当前仅当两个人为朋友时，才能视为一个团伙。
• 问一共有多少个团伙。

分析

1. 与a为直接朋友的人，属于同一个团伙；因此我们只需要进行一次merge(a,b)操作即可。
2. 如果a与b互为敌人。则与b为直接敌人的所有敌人属于同一个团伙。则与a为直接敌人的所有敌人属于同一个团伙。

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int p[N]; //存储f[i]的父亲节点
int e[N]; //存储i的的敌人(相互存储)

//询问所属集合
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}

//合并
void merge(int a,int b){
    if(find(a)!=find(b)) p[find(b)] = find(a);  //b挂到a的祖宗节点上
}

int main(){
    int n,m;
    cin>>n>>m;

    //初始化
    for(int i=1;i<=n;i++) p[i] = i;

    while(m--){
        char c;
        int a,b;
        cin>>c>>a>>b;

        //如果a与b为直接朋友，直接合并集合即可
        if(c=='F')  merge(a,b);
        else if(c=='E'){
            //如果a与b为直接敌人，
            //记录b的敌人团伙的带头大哥为a，此后b的敌人会与a合并
            //记录a的敌人团伙的带头大哥为b，此后a的敌人会与b合并
            if(!e[a]) e[a] = b;
            if(!e[b]) e[b] = a;
            merge(p[b],e[a]);
            merge(p[a],e[b]);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        if(p[i]==i) res++;
    }
    cout<<res<<endl;

    return 0;
}