P1892. 团伙

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 453 阅读时长 ≈ 2 分钟

考点

  • 扩展域并查集

题解

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
#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e3 + 10;
int n, m, p, q, fa[LEN << 1];

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

void join(int x, int y) {
  int a = find(x), b = find(y);
  fa[a] = b;
}

int main() {
  char ch;
  cin >> n >> m;
  for (int i = 1; i <= (n << 1); ++i) fa[i] = i;
  for (int i = 1; i <= m; ++i) {
    cin >> ch >> p >> q;
    if (ch == 'F') {
      join(p, q);
    } else {
      join(q + n, p), join(p + n, q);
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    if (fa[i] == i) ++ans;
  cout << ans;
  return 0;
}

思路

典型的扩展域并查集

每个人都有两种关系属性，我的朋友和我的敌人，所以fa数组应该多开一倍

1 ~ n的范围存储我的朋友这一关系，n + 1 ~ 2n的范围存储我的敌人这一关系

题目给了两个关系传递要求：

  • 朋友的朋友是朋友

    p和q直接合并即可

  • 敌人的敌人是朋友

    对于p而言，它的敌人关系对应p + n，那么q应与p + n同处一集合

    同样的，对于q而言，它的敌人关系对应q + n，那么p应于q + n同处一集合

    考虑以下样例：

    E 1 2

    E 2 6

​ 设字符{}代表同一集合，根据上述描述有：

​ {1+n, 2}、{2+n, 1}、{2+n, 6}、{6+n, 2}

​ 是满足题目要求的

这里还有一个小Trick，合并的时候应让朋友关系设置为敌人关系的祖先，而不能颠倒：

1
join(q + n, p), join(p + n, q);

两者颠倒从效果上看并不会有差异，无论怎样二者都将同处一集合

但朋友关系设为敌人关系的祖先，最终统计连通块个数会更方便，只需一次遍历判断fa[i] == i即可