团伙

题目描述
在某城市里住着n 个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、一个人的朋友的朋友是他的朋友。
2、一个人敌人的敌人是他的朋友。
3、一个人和他所有的朋友在同一个团伙。
4、一个人的所有敌人是同一个团伙。
告诉你关于这n 个人的m 条信息（即某两人是朋友，或者某两个人是敌人），请你计算出这个城市的人最多有多少个团伙。

输入
第一行：n（2<=n<=1000）,m（1<=m<=5000）,中间一个空格隔开。
以下共m 行，每行的格式是：d x y，三个数中间一空格隔开，d=0：x 和y 是朋友，d=1：x和y 是敌人。

输出
N 个人最多组成了多少个团伙。

样例输入
6 4
1 1 4
0 3 5
0 4 6
1 1 2

样例输出
3

提示
5
说明：{1}, {2, 4, 6}, {3, 5}共3 个团伙

从题中的描述就可以判断出这是一道并查集题。

首先，对于两人是朋友，就合并所在集合。对于两个人是敌人，比如a是b的敌人，那么就应该合并a和b的敌人所在的集合。同理，也要合并b和a的敌人所在的集合。

那么可以开一个数组en[]，en[i] = j 表示 i 的敌人是 j。那么若 i 和 j 是敌人，就应该合并 i 和en[j] 以及 j 和 en[i]。

另一种表示敌人的方法是 i + n。就是合并 i 和 j + n 以及 j 和 i + n。

给出第一个方法的代码

 1 #include<cstdio>
 2 #include<iostream> 
 3 #include<cstring> 
 4 #include<cmath>
 5 #include<algorithm> 
 6 using namespace std;
 7 const int maxn = 1e4 + 5;
 8 int p[maxn], en[maxn];
 9 int n, m, ans = 0;
10 void init()
11 {
12     for(int i = 0; i < maxn; ++i) {p[i] = i; en[i] = 0;}
13 }
14 int Find(int x)
15 {
16     return p[x] == x ? x : p[x] = Find(p[x]);
17 }
18 void merge(int x, int y)
19 {
20     int px = Find(x), py = Find(y);
21     if(px == py) return;
22     else {p[px] = py; return;}
23 }
24 int main()
25 {
26     freopen("group.in", "r", stdin);
27     freopen("group.out", "w", stdout);
28     init();
29     scanf("%d%d", &n, &m);
30     for(int i = 1; i <= m; ++i)
31     {
32         int d, a, b; scanf("%d%d%d", &d, &a, &b);
33         if(!d) merge(a, b);
34         else                        
35         {
36             if(!en[a]) en[a] = b;        //a还没有敌人，就将b作为a的敌人所在集合的代表元素 
37             else merge(b, en[a]); 
38             if(!en[b]) en[b] = a;
39             else merge(a, en[b]);         
40         }
41     }
42     for(int i = 1; i <= n; ++i) if(p[i] == i) ans++;
43     printf("%d
", ans);
44 }