问题标题: 酷町堂：1315 团伙

颓到问作业（还是并查集板子的亿丢丢变形）~~### rp--

1315   团伙

经验值：2000 时间限制：2000毫秒

题目描述 Description

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

输入描述 Input Description

第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是敌人。

输出描述 Output Description

一个整数，表示这n个人最多可能有几个团伙。

样例输入 Sample Input

6 4 1 1 4 0 3 5 0 4 6 1 1 2

样例输出 Sample Output

3

WA90?8ms？估计99.99%的可能性调挂

#include <iostream>
#include <cstring>

using namespace std;

int n, m;
int fa[1005];
int g[1005][1005];
bool t[1005];

void init() {
    for(int i=1; i<=n; i++) {
        fa[i] = i;
    }
}
int find(int x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}
void unite(int a, int b) {
    int x = find(a);
    int y = find(b);
    if(x == y) return;
    fa[x] = y;
}
bool same(int a, int b) {
    return find(a) == find(b);
}
int main() {
    memset(g, -1, sizeof(g));
    cin >> n >> m;
    init();
    for(int i=1; i<=m; i++) {
        int p, x, y;
        cin >> p >> x >> y;
        g[x][y] = p;
    }
    for(int i=1; i<=n; i++) {
        int Last = -1;
        for(int j=1; j<=n; j++) {
            if(g[i][j] == 0) {
                unite(i, j);
            } else if(g[i][j] == 1){
                if(Last != -1) {
                    unite(Last, j);
                }
                Last = j;
            }
        }
    }
    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(i == find(i)) {
            ans ++;
        }
    }
    cout << ans;
    return 0;
}

重金（50豆子）

重金（50豆子）

重金（50豆子）

@kdt所有巨佬