大佬求助!!有点逻辑上的问题
查看原帖
大佬求助!!有点逻辑上的问题
763077
Pjkang楼主2023/7/11 22:05

在 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();
}
2023/7/11 22:05
加载中...