Luogu1892 [BOI2003]团伙

Link

题解

这个跟食物链那道题很像，要用到扩展域并查集

首先这道题给出了两种关系，分别是朋友和敌人，并且给出了唯二的两种判定方式

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

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

因此，我们可以将并查集的大小扩大一倍，[1,n] 表示朋友关系的集合，[n+1, n * 2] 表示敌人关系集合

那么，如果两个人是朋友，我们可以把他们各自的朋友集合并起来，因为显然易见，朋友的朋友还是朋友。

当两个人是敌人关系的时候，我们就把 x 的敌人集合与 y 的朋友集合并在一起，对于 y 同理进行同样的操作。

上码

Code

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2000 + 5;

int n, Q;
int fa[SIZE], vis[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }

inline void Unite(int x, int y)
{
    int fx = Find(x), fy = Find(y);
    if (fx != fy) fa[fx] = fy;
}

int main()
{
    char ch;
    int x, y;
    n = read(), Q = read();
    for (int i = 1; i <= n * 2; i++) fa[i] = i;
    while (Q--) {
        std::cin >> ch >> x >> y;
        if (ch == 'E') {
            Unite(x + n, y);
            Unite(y + n, x);
        }
        if (ch == 'F')
            Unite(x, y); //朋友直接并起来
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
        if (fa[i] == i) ++cnt;
    printf("%d", cnt);
    return 0;
}