个人技术分享

$1920$ 年的芝加哥，出现了一群强盗。

现在，我们给出一些强盗之间的两两关系信息。

给出的信息中，涉及到的关系有两种：朋友和敌人。

而且有一点是肯定的，就是：

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

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

两个强盗在同一团伙内的条件是当且仅当他们是朋友。

根据给出的强盗们的信息，请你计算最多有多少个强盗团伙。

输入格式

第一行包含整数 $N$，表示强盗的个数（从 $1$ 编号到 $N$）。

第二行包含整数 $M$，表示关于强盗的信息条数。

接下来 $M$ 行，每行可能是 F p q 或是 E p q，$F$ 表示 $p$ 和 $q$ 是朋友，$E$ 表示 $p$ 和 $q$ 是敌人。

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

输出格式

输出只有一行，表示最大可能的团伙数。

数据范围

$2\le N\le 1000$,
$1\le M\le 5000$,
$1\le p,q\le N$

输入样例

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

输出样例

3

思路

这道题就是敌人的敌人是朋友，我们用扩展域。扩展域，顾名思义，就是扩展两倍的空间。

AC 代码

//敌人的敌人是朋友

#include<iostream>
#include<algorithm>

using namespace std;

const int N = 1010,M = 5010;

struct E{
    int x,y;
}e[M];
int n,m;
int p[M];

int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}

int main(){
    cin>>n>>m;
    
    for(int i=1;i<=n*2;i++)p[i]=i;
    
    for(int i=1;i<=m;i++){
        char op;
        int a,b;
        cin>>op>>a>>b;
        if(op=='F'){
            p[find(a)]=find(b);
        }else{
            p[find(a+n)]=find(b);
            p[find(b+n)]=find(a);
        }
    }
    
    
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(p[i]==i){
            cnt++;
        }
    }
    
    cout<<cnt<<endl;
    
    return 0;
    
}