算法题：团伙

问题描述

在某城市里住着n个人，任何两个认识的人不是朋友就是敌人，而且满足：
1、我朋友的朋友是我的朋友；
2、我敌人的敌人是我的朋友；
所有是朋友的人组成一个团伙。告诉你关于这n个人的m条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？

输入格式

第1行为n和m，1<n<1000,1≤m≤100000；
以下m行，每行为pxy，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

解决方案

思路

并查集

代码

#include <iostream>

using namespace std;
int n, m;
int fr[1005], en[1005][1005];

void init() {
    for (int i = 1; i <= n; ++i) {
        fr[i] = i;
    }
}

int find(int a) {
    if (fr[a] == a) return a;
    return fr[a] = find(fr[a]);
}

void join(int a, int b) {
    int x = find(a);
    int y = find(b);
    fr[x] = y;
}

int main() {
    cin >> n >> m;

    init();
    for (int i = 0; i < m; ++i) {
        int p, x, y;
        cin >> p >> x >> y;
        if (p) {    // 为敌人时
            // 并入敌人的敌人中
            for (int j = 1; j <= en[x][0]; ++j) {
                join(y, en[x][j]);
            }
            for (int j = 1; j <= en[y][0]; ++j) {
                join(x, en[y][j]);
            }

            //记录新的敌人
            en[x][++en[x][0]] = y;
            en[y][++en[y][0]] = x;

        } else {    // 为朋友时
            join(x, y);
        }
    }

    int count = 0;
    for (int i = 1; i <= n; ++i) {
        if (find(i) == i) {
            count++;
        }
    }
    cout << count << endl;
    return 0;
}