洛谷P1892《[BOI2003]团伙》

七月 28, 2018 2871

本题来自「2018 SDSC」Day 3 考试题目

题目链接

题目描述

1920年的芝加哥，出现了一群强盗。如果两个强盗遇上了，那么他们要么是朋友，要么是敌人。而且有一点是肯定的，就是：

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

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

两个强盗是同一团伙的条件是当且仅当他们是朋友。现在给你一些关于强盗们的信息，问你最多有多少个强盗团伙。

Input/Output 格式 & 样例

输入格式

输入文件gangs.in的第一行是一个整数N(2<=N<=1000)，表示强盗的个数（从1编号到N）。

第二行M(1<=M<=5000)，表示关于强盗的信息条数。

以下M行，每行可能是F p q或是E p q（1<=p q<=N），F表示p和q是朋友，E表示p和q是敌人。

输入数据保证不会产生信息的矛盾。

输出格式

输出文件gangs.out只有一行，表示最大可能的团伙数。

输入样例

1
2
3
4
5
6
6
4
E 1 4
F 3 5
F 4 6
E 1 2

输出样例

1
3

解题思路

很显然这是一道并查集的题目

初始时我们把每一个人单独列为一个团伙

由题可得，这道题主要有如下合并方式：

  1. 我的朋友是我的朋友
  2. 我的朋友的朋友是我的朋友
  3. 我的敌人的朋友是我的敌人
  4. 我的敌人的敌人是我的朋友

那么我们要另开一个 Enemy[\ ] 数组， Enemy[i] 表示 i 的其中一个敌人

每次合并敌人的时候，先判断是否有记录过敌人：

  • 如果有，那么就把当前的敌人和记录的敌人合并在一个团伙里
  • 如果没有，那么就把当前的敌人记录

最后开一个数组 count[\ ] 进行统计

这里要注意几个点：

  1. 开始时并查集数组要开两倍，因为你要把敌人和朋友存在一个数组里
  2. 合并敌人时要注意合并的不是敌人本身，而是 Find( 敌人 )
  3. 最后统计的时候也要统计 Find( 敌人 )

对了，注意输入…

建议使用iostream…

别问我为什么会写上这句话

53vhll.png

代码实现

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
using namespace std;

const int MAXN = 1000 + 10;

int U[MAXN * 2], Enemy[MAXN * 2], n, m;
int count[MAXN * 2], cnt;

inline int getint() {
    int s = 0, x = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') x = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        s = s * 10 + ch - '0';
        ch = getchar();
    }
    return s * x;
}

inline void putint(int x) {
    if (x < 0) {
        x = -x;
    }
    if (x >= 10) {
        putint(x / 10);
    }
    putchar(x % 10 + '0');
}

int Find(int x) {
    if (U[x] == x) return x;
    return U[x] = Find(U[x]);
}

void Union(int x, int y) {
    x = Find(x), y = Find(y);
    if (x == y) return;
    U[x] = y;
    return;
}

int main(int argc, char *const argv[]) {
    freopen("P1892.in", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i <= n * 2; ++i) U[i] = i;
    for (int i = 1; i <= m; ++i) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        switch(c) {
            case 'F': {
                Union(x, y);
                break;
            }
            case 'E': {
                if (Enemy[x] == 0) Enemy[x] = Find(y);
                else Union(y, Enemy[x]);
                if (Enemy[y] == 0) Enemy[y] = Find(x);
                else Union(x, Enemy[y]);
            }
        }
    }
    for (int i = 1; i <= n; ++i) ++count[Find(i)];
    for (int i = 1; i <= n; ++i) if (count[i]) ++cnt;
    printf("%d\n", cnt);
    return 0;
}