【Baltic2003】【BZOJ1370】Gang团伙（并查集，拆点）

problem

• 给定n个人
• 朋友的朋友是朋友，敌人的敌人是朋友
• 朋友之间组成一个团伙，求团伙数

solution

• 将每个点x拆成两个：x和x+n（分别表示x的朋友和敌人）
• 如果x和y是朋友，就将x和y合并
• 如果x和y是敌人，就将x和y+n合并，将y和x+n合并
• 注意朋友的敌人不一定是敌人，因此如果x和y是朋友，不能将x+n和y+n合并

codes

#include<iostream>
#include<algorithm>
#define maxn 1010
using namespace std;

//UnionFindSet
int fa[maxn<<1];
void init(int n){for(int i = 1; i <= n; i++)fa[i]=i;}
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x, int y){x=find(x);y=find(y);if(x==y)return;fa[x]=y;}

int main(){
    int n, m;
    cin>>n>>m;
    init(maxn<<1);
    for(int i = 1; i <= m; i++){
        char op;  int x, y;
        cin>>op>>x>>y;
        if(op=='F'){
            merge(x,y);
            //merge(x+n,y+n);
        }else{
            merge(x,y+n);
            merge(x+n,y);
        }
    }
    int a[maxn];
    for(int i = 1; i <= n; i++)
        a[i]=find(i);
    sort(a+1,a+n+1);
    int ans = 0;
    for(int i = 1; i <= n; i++)
        if(i==1 || a[i]!=a[i-1])
            ans++;
    cout<<ans<<'\n';
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80525024