Luogu P1892 [BOI2003]团伙

题目描述

https://www.luogu.com.cn/problem/P1892

并查集裸题复习

Solution

需要注意本题只需要考虑敌人的敌人是朋友，不需要考虑敌人的朋友的关系

所以我们只需要拿并查集记录一下朋友集合，然后每个人记录第一个敌人即可（因为后续的敌人和第一个敌人是朋友

#include <iostream>
#include <cstdio>
#define maxn 1010
using namespace std;

int n, m, e[maxn];

int fa[maxn];
void init_fa() { for (int i = 1; i <= n; ++i) fa[i] = i; }

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

inline void merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return ;
    fa[fx] = fy;
}

inline void solve_1() {
    int x, y; scanf("%d%d", &x, &y);
    merge(x, y);
}

inline void solve_2() {
    int x, y; scanf("%d%d", &x, &y);
    if (!e[x]) e[x] = y;
    else merge(e[x], y);
    if (!e[y]) e[y] = x;
    else merge(e[y], x); 
}

int main() {
    cin >> n >> m; init_fa(); 
    for (int i = 1; i <= m; ++i) {
        char ch[5]; scanf("%s", &ch);
        switch (ch[0]) {
        case 'F' : solve_1(); break;
        case 'E' : solve_2(); break;
        }
    } int ans = 0;
    for (int i = 1; i <= n; ++i) ans += find(i) == i;
    cout << ans << endl; 
    return 0; 
}