在 ch == 'F'时,x和y是朋友那么需要unite(x, y),但与题解不同的是:我加了一句unite(x+n, y+n);因为逻辑上来说x的敌人与x的朋友的敌人应该是朋友;
具体代码如下,其中unite函数还特意让小于n的数为根(如有错误,希望大佬指出);我想知道为什么不对呀。
#include <bits/stdc++.h>
using namespace std;
int par[3001];
int n, m;
int find(int x) {
if (par[x] == x) return x;
else return par[x] = find(par[x]);
}
void unite(int x, int y) {
x = find(x);
y = find(y);
par[max(x, y)] = min(x, y);
}
void solve() {
cin >> n >> m;
for (int i = 0; i <= 2*n; i++) par[i] = i;
while (m--) {
char op; int x, y;
cin >> op >> x >> y;
if (op == 'F') {
unite(x, y);
unite(x+n, y+n); // 我就加了这一句过不了,按照逻辑来说,应该加上这一句呀;“朋友的敌人就是自己敌人的朋友”
}
else {
unite(x+n, y);
unite(y+n, x);
}
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
if (par[i] == i) cnt++;
}
cout << cnt << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}