【洛谷】P1892 [BalticOI 2003] 团伙

题目链接：P1892 [BalticOI 2003] 团伙

思路

除了并查集外，还要记录每个人之间的关系，典型的扩展域并查集模板题。

代码

写的时候用了秩优化，能优化一些效率。

//
// Created by xiaoeyv on 2025/6/19.
//

#define maxn 1010
#define maxm 5010
#include<bits/stdc++.h>
using namespace std;

int n, m;
int pre[maxn * 2], r[maxn * 2];

int find(int x) {
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}

void join(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry)
        return;
    if (r[rx] < r[ry])
        pre[rx] = ry;
    else {
        pre[ry] = rx;
        if (r[rx] == r[ry])
            r[rx]++;
    }
}

int main() {
    cin >> n >> m;
    memset(r, 0, sizeof(r));
    for (int i = 1; i <= n * 2; i++) {
        pre[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        char op;
        int p, q;
        cin >> op >> p >> q;
        if (op == 'F') {
            join(p, q);
        } else {
            join(p + n, q);
            join(p, q + n);
        }
    }
    set<int> ans;
    for (int i = 1; i <= n; i++) {
        ans.insert(find(i));
    }
    cout << ans.size() << endl;
    return 0;
}