题解
这个跟食物链那道题很像,要用到扩展域并查集
首先这道题给出了两种关系,分别是朋友和敌人,并且给出了唯二的两种判定方式
我朋友的朋友是我的朋友;
我敌人的敌人也是我的朋友。
因此,我们可以将并查集的大小扩大一倍,[1,n] 表示朋友关系的集合,[n+1, n * 2] 表示敌人关系集合
那么,如果两个人是朋友,我们可以把他们各自的朋友集合并起来,因为显然易见,朋友的朋友还是朋友。
当两个人是敌人关系的时候,我们就把 x 的敌人集合与 y 的朋友集合并在一起,对于 y 同理进行同样的操作。
上码
Code
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 2000 + 5;
int n, Q;
int fa[SIZE], vis[SIZE];
inline int read()
{
char ch = getchar();
int f = 1, x = 0;
while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
return x * f;
}
inline int Find(int x) { return x == fa[x] ? x : fa[x] = Find(fa[x]); }
inline void Unite(int x, int y)
{
int fx = Find(x), fy = Find(y);
if (fx != fy) fa[fx] = fy;
}
int main()
{
char ch;
int x, y;
n = read(), Q = read();
for (int i = 1; i <= n * 2; i++) fa[i] = i;
while (Q--) {
std::cin >> ch >> x >> y;
if (ch == 'E') {
Unite(x + n, y);
Unite(y + n, x);
}
if (ch == 'F')
Unite(x, y); //朋友直接并起来
}
int cnt = 0;
for (int i = 1; i <= n; i++)
if (fa[i] == i) ++cnt;
printf("%d", cnt);
return 0;
}
Comments | NOTHING