题目描述

此题的朋友的朋友是很好理解的，只要是我的朋友，我们就是一个team，进行Union操作。但是敌人的敌人也是我们的朋友，怎么考量呢？我们需要为此增加一个f数组，存储我的敌人的大哥，很好理解，a和b是敌人的话，b和c是敌人的话，那么a和c应该是一个team的，此处需要对a和c进行Union操作，我们第一次存储的敌人是一个参考，判断哪些人应该合并。

算法1

(遍历一次即可，并查集的查找和合并均为o(1)) $O(n)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

class UnionFind{
public:
    vector<int> father;
    UnionFind(int num) {
        for(int i = 0; i < num; i ++ ) father.push_back(i);
    }
    int find(int n)
    {
        if(n == father[n]) return n;
        return father[n] = find(father[n]);
    }
    void Union(int a, int b)
    {
        int fa = find(a);
        int fb = find(b);
        if( fa != fb ) father[fb] = fa;
    }
};

int main()
{
    int N, M;
    cin >> N >> M;

    UnionFind UF(N + 1);
    vector<int> f(N + 1, 0);

    while(M -- )
    {
        char ch;
        int a, b;
        cin >> ch >> a >>b;
        if(ch == 'F')
            UF.Union(a, b);
        else
        {
            if(!f[a])
                f[a] = UF.find(b);
            else UF.Union(b, f[a]);
            if(!f[b])
                f[b] = UF.find(a);
            else UF.Union(a, f[b]);
        }
    }

    int cnt = 0;
    vector<int> st(N + 1, 0);

    for(int i = 1; i <= N; i ++ )
        if(! st[UF.find(i)])
        {
            cnt ++;
            st[UF.father[i]] ++;
        }

    cout << cnt << endl;

    return 0;
}