记录编号	549851	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]犯罪团伙	最终得分	100
用户昵称	ZooxTark➲	是否通过	通过
代码语言	C++	运行时间	0.117 s
提交时间	2020-02-25 16:03:26	内存使用	17.48 MiB

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

bool Enemy[2001][2001];
class UnionFindSet
{
private:
    int MainSet[2001];
    int Maxn;
    int FindRoot(int Number)
    {
        return  MainSet[Number] = ((MainSet[Number] == Number)? Number : FindRoot(MainSet[Number]));
    }
public:
    void Reset(int Number)
    {
        Maxn = Number;
        memset(MainSet,-1,sizeof(MainSet));
        memset(Enemy,false,sizeof(Enemy));
        for(int i = 0;i <= Number;i++)
        {
            MainSet[i] = i;
        }
    }
    void Union(int num1,int num2,char text)
    {
        if(text == 'F')
            MainSet[FindRoot(num1)] = MainSet[FindRoot(num2)];
        else
        {
            Enemy[num1][num2] = Enemy[num2][num1] = true;
            for(int i = 0;i < Maxn;i++)
                if(Enemy[num1][i])
                    MainSet[FindRoot(i)] = MainSet[FindRoot(num2)];
            for(int i = 0;i < Maxn;i++)
                if(Enemy[num2][i])
                    MainSet[FindRoot(i)] = MainSet[FindRoot(num1)];
        }
    }
    int CountSet()
    {
        bool vis[2001];
        memset(vis,false,2001);
        int Count = 0;
        for(int i = 1;i <= Maxn;i++)
        {
            int iTemp = FindRoot(i);
            if(!vis[iTemp])
            {
                Count++;
                vis[iTemp] = true;
            }
        }
        return Count;
    }
};

int main()
{
    ifstream fin("crime.in");
    ofstream fout("crime.out");
    int n,m;
    fin >> n >> m;
    char c;
    int a,b;
    UnionFindSet UFS;
    UFS.Reset(n);
    for(int i = 0;i < m;i++)
    {
        fin >> c >> a >> b;
        UFS.Union(a,b,c);
    }
    fout << UFS.CountSet();
    return 0;
}