蒟蒻求调
查看原帖
蒟蒻求调
1567495
txdt楼主2025/1/4 20:01

使用了并查集,但是有很多不能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;
}
2025/1/4 20:01
加载中...