TZOJ 5784: 团伙 并查集

描述

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：

1、我朋友的朋友是我的朋友；

2、我敌人的敌人是我的朋友；

所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

输入

第1行为n和m，1<n<1000,1≤m≤100 000；

以下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

思路：对于朋友，直接并集，对于敌人，那么需要将所有敌人用二维数组存储起来，a[x][0]的数值代表x的敌人数量，然后让敌人并集

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 1005;
 4 int a[N][N],f[N];
 5 int p,x,y;
 6 int find(int x)
 7 {
 8     if(f[x]!=x)f[x] = find(f[x]);
 9     return f[x];
10 }
11 void merger(int x,int y)
12 {
13     f[y] = x;
14 }
15 int main()
16 {
17     int n,m;
18     cin>>n>>m;
19     for(int i=1;i<=n;i++)f[i] = i;
20     for(int i=1;i<=m;i++)
21     {
22         cin>>p>>x>>y;
23         if(p==0)
24         {
25             if(find(x)!=find(y))
26                 merger(x,y);
27         }
28         else //a[x][0]代表x有a[x][0]个敌人，遍历敌人数量，然后将敌人和y并集 
29         {
30             for(int j=1;j<=a[x][0];j++) //y和x的敌人并集 
31             {
32                 int fa = find(y);
33                 int fb = find(a[x][j]);
34                 if(fa!=fb)merger(fa,fb);
35             }
36             for(int j=1;j<=a[y][0];j++) //x和y的敌人并集 
37             {
38                 int fa = find(x);
39                 int fb = find(a[y][j]);
40                 if(fa!=fb)merger(fa,fb);
41             }
42             a[x][++a[x][0]] = y; //将y加入x的敌人 
43             a[y][++a[y][0]] = x; //将x加入y的敌人 
44             
45         }
46     }
47     int ans = 0;
48     for(int i=1;i<=n;i++)
49         if(f[i]==i)ans++;
50     cout<<ans;
51      return 0;
52 }