使用了并查集,但是有很多不能AC,求大佬看看
#include <bits/stdc++.h>
using namespace std;
class UnionFind
{
public:
vector<int> parent, rank;
vector<int> enemy;
UnionFind(int N)
{
parent.resize(N);
rank.resize(N, 0);
enemy.resize(N, -1);
iota(parent.begin(), parent.end(), 0);
}
int find(int x)
{
if (parent[x] != x)
{
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y)
{
int xroot = find(x);
int yroot = find(y);
if (xroot != yroot)
{
if (rank[xroot] < rank[yroot])
parent[yroot] = xroot;
else if (rank[xroot] > rank[yroot])
parent[xroot] = yroot;
else
{
parent[yroot] = xroot;
rank[xroot] ++;
}
}
}
void set_enemy(int x, int y)
{
int xr = find(x);
int yr = find(y);
if(enemy[xr] == -1)
enemy[xr] = yr;
else
unite(enemy[xr], yr);
if(enemy[yr] == -1)
enemy[yr] = xr;
else
unite(enemy[yr], xr);
}
};
int main()
{
int n, m;
cin >> n >> m;
UnionFind uF(n);
for (int i = 0; i < m; i++)
{
char opt;
int p, q;
cin >> opt >> p >> q;
p--;
q--;
if (opt == 'F')
uF.unite(p, q);
else if (opt == 'E')
uF.set_enemy(p, q);
}
unordered_set<int> groups;
for (int i = 0; i < n; i++)
groups.insert(uF.find(i));
cout << groups.size() << endl;
return 0;
}