CodeForces-177C1 题解

发表于2023-04-09更新于2023-04-09

题目传送门

一道简单的并查集练手题……

与普通的并查集不同，除此之外还需记录下来某两人的讨厌关系，使得他们不能在同一集合中。

1
if (find_root(x) == find_root(y)) vis[find_root(x)] = 1;

剩下的就是并查集了，神犇可以直接跳过。

查找根：

1
2
3
4
int find_root(int n) {
    if (fa[n] == n) return n;
    return fa[n] = find_root(fa[n]);
}

合并：

1
2
3
4
void merge(int x, int y) { 
    int sx = find_root(x), sy = find_root(y);
    if (sx != sy) fa[sx] = sy;
}

预处理：

1
for (int i = 1; i <= n; i++) fa[i] = i;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, k, m, ans; // ans 需初始化为 0
int cnt[2005], fa[2005]; 
bool vis[2005]; // 标记
int find_root(int n) { // 查找根
    if (fa[n] == n) return n;
    return fa[n] = find_root(fa[n]);
}
void merge(int x, int y) { // 合并
    int sx = find_root(x), sy = find_root(y);
    if (sx != sy) fa[sx] = sy;
}
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) fa[i] = i; // 预处理
    for (int i = 1; i <= k; i++) {
        int u, v;
        cin >> u >> v;
        merge(u, v);
    }
    for (int i = 1; i <= n; i++) cnt[find_root(i)]++; // 统计派对人数
    cin >> m;
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        if (find_root(x) == find_root(y)) vis[find_root(x)] = 1; // 标记关系
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[find_root(i)]) ans = max(ans, cnt[find_root(i)]); // 如果没有讨厌的人就更新最大值
    }
    cout << ans;
    return 0;
}