BZOJ 1370: [Baltic2003]Gang团伙 [并查集 拆点 | 种类并查集WA]

题意：

朋友的朋友是朋友，敌人的敌人是朋友；朋友形成团伙，求最多有多少团伙

---

种类并查集WA了一节课，原因是，只有那两种关系才成立，诸如朋友的敌人是朋友之类的都不成立！

所以拆点做吧

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=1005;
typedef long long ll;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n, m, fa[N], val[N], x, y, cc[N][2]; char s[5];
inline int find(int x) {
    if(x == fa[x]) return x;
    int root = find(fa[x]);
    val[x] ^= val[fa[x]];
    return fa[x] = root;
}
inline void Union(int x, int y, int p) { 
    int f1 = find(x), f2 = find(y);
    if(f1 != f2) {
        fa[f1] = f2;
        val[f1] = val[x]^val[y]^p;
    } else {
        if( (val[x]^val[y]) != p) while(1);
    }
}


int main() {
    freopen("in","r",stdin);
    n=read(); m=read();
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=m; i++) {
        scanf("%s",s); x=read(), y=read();
        Union(x, y, s[0] == 'F' ? 0 : 1);
    }
    int ans=0;
    for(int i=1; i<=n; i++) cc[find(i)][val[i]] = 1;
    for(int i=1; i<=n; i++) ans += cc[i][0] + cc[i][1];
    printf("%d",ans);
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=2005;
typedef long long ll;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n, m, fa[N], x, y, a[N], ans; char s[5];
inline int find(int x) {return x==fa[x] ? x : fa[x]=find(fa[x]);}
inline void Union(int x, int y) {
    x = find(x), y = find(y);
    if(x != y) fa[x] = y;
}

int main() {
    freopen("in","r",stdin);
    n=read(); m=read();
    for(int i=1; i<=n*2; i++) fa[i]=i;
    for(int i=1; i<=m; i++) {
        scanf("%s",s); x=read(), y=read();
        if(s[0]=='F') Union(x, y);
        else Union(x, y+n), Union(x+n, y);
    }
    for(int i=1; i<=n; i++) a[i]=find(i);
    sort(a+1, a+1+n); ans=unique(a+1, a+1+n) - a - 1;
    printf("%d",ans);
}