校园内有很多白社会团伙，他们专做好事。经过长期的卧底，scy知道：学校有n个人，任何两个认识的人不是朋友就是敌人，而且满足：①我朋友的朋友是我的朋友；②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在拥有关于这n个人的m条信息（即某两个人是朋友，或某两个人是敌人），请你计算出这个城市最多可能有多少个白社会团伙。
数据范围：2≤N≤2000，1≤M≤5000。
输入数据
第一行包含一个整数N，第二行包含一个整数M，接下来M行描述M条信息，内容为以下两者之一：“F x y”表示x与y是朋友；“E x y”表示x与y是敌人（1≤x≤y≤N）。
输出数据
包含一个整数，即可能的最大团伙数。
样例：
输入：
6
4
E 1 4
F 3 5
F 4 6
E 1 2
输出:
3
2360: 校园白社会
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
提示
分析：
本题看起来很简单，但很容易就会得出错误的算法。由第一条性质可知朋友具有传递性，可把一个团伙看成一个等价类。但是第二条容易产生误导，“我敌人的敌人是朋友”，似乎只能有两个团伙，即某人i的朋友组成一个团伙，他的敌人组成另一个团伙。但是不要忘了，i还有不认识的人，我们的任务就是把这些人分成尽量多的团伙。
对于朋友信息，可以一一进行集合合并，但是对于敌人信息就没有这么好办了。我们需要给每个集合i记录它的“敌人集合”e[i]，当收到i和j是敌人的信息后，把i和e[j]合并，j和e[i]合并，注意正确处理和空集合并、自己跟自己合并这两种特殊情况。最后，等价类的个数就是所求答案。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版