BZOJ 1370: [Baltic2003]Gang团伙 – [并查集]

题目传送门(BZOJ)
>原文链接<

题解 :

只要考虑如何维护题中所述的两个关系就好了。

  1. 我朋友的朋友也是我的朋友

    —— 并查集,这三个人只要在同一个集合里,就意味着他们都是朋友。

    1. 我敌人的敌人是我的朋友。

    ——我们把每个人拆点,如果 ab 是敌人,那么把 a’b 并到一个集合里,b’a 同理。

    这样如果再有人是 a 的敌人,就会和 a’ 合并,也就是 b 的朋友了

最后统计一下前 n 个点中有多少个不同的集合就可以辣。

代码 :

#include 
#include 
#include 
using namespace std;
const int N = 2100;
int fa[N], a[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n*2; i ++ ) fa[i] = i;
    for(int i = 1; i <= q; i ++ ) {
        char opt[3];
        scanf("%s", opt);
        if(opt[0] == 'E') {
            int x, y;
            scanf("%d%d", &x, &y);
            fa[find(x+n)] = find(y);
            fa[find(y+n)] = find(x);
        }
        else {
            int x, y;
            scanf("%d%d", &x, &y);
            fa[find(x)] = find(y);
        }
    }
    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(a[i] != a[i-1]) ans ++ ;
    printf("%d\n", ans);
}

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注