【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
#include
#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<'\n';
    return 0;
}
点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像