SSOJ2448团伙
3274+
作者：crxis 发布：2017-09-16 分类：并查集
题目大意：n个人，任何两个认识的人不是朋友就是敌人，我朋友的朋友是我的朋友，我敌人的敌人是我的朋友，最多有多少个朋友集合？
题目描述
在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
（1）我朋友的朋友是我的朋友；
（2）我敌人的敌人是我的朋友。
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？
输入
第1行为n和m，1<n<1000,1<=m<=1000；
以下m行，每行为p，x，y，p的值为0或1，p为0时，表示x和y是朋友，p为1时，表示x和y是敌人。两个整数之间用一个空格隔开。
输出
一个整数，表示这n个人最多可能有几个团伙。
样例输入
6 4
1 1 4
0 3 5
0 4 6
1 1 2
样例输出
3
解题思路
如果两个人是朋友，直接用并查集合并在一起；如果两个人是敌人，就将敌人的敌人合并在一起。关键是敌人的敌人怎么合并？如果只有一个敌人，不需要合并；如果有两个敌人，就把这两个敌人合并在一起；如果有k个敌人，由于之前k-1个敌人已经合并在一起，只需要将第k个敌人和之前k-1个中的任意一个敌人合并即可。
程序1中，f记录敌人的父亲/祖先，d记录敌人。如果不想开敌人数组，还可以将f数组开大一点，用i+n表示敌人，这样如果p和q是敌人，只需要将p和q+n合并在一起、p+n和q合并在一起。由于最后统计有多少个团伙，只统计n个人中有多少个自己是祖先，故程序2中，合并敌人时，必须让编号小的做祖先（前n个点做祖先）。
程序实现
