关于种族并查集
查看原帖
关于种族并查集
361592
histcat楼主2022/7/20 19:49

此代码如果在if(opt == 'F')大括号中加了一行un(a + n, b + n)就会导致wa,(关于种族并查集了解的不是太深),有dalao能给解释一下吗 AC

WA

#include<iostream>
#include<cstdlib>
#include<cstdio>

using namespace std;
int n, m;
char opt;
const int N = 2e3 + 10;
int fa[N << 1];

int find(int x)
{
    if(fa[x] == x)
    {
        return x;
    }
    else
    {
        return fa[x] = find(fa[x]);
    }
}

void un(int x, int y)
{
    int t1 = find(x), t2 = find(y);
    if(t1 != t2)
    {
        fa[t2] = t1;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for(int i = 1;i <= (n << 1);i++)
    {
        fa[i] = i;
    }
    int a, b;

    for(int i = 1;i <= m;i++)
    {
        cin >> opt >> a >> b;
        if(opt == 'F')
        {
            un(a, b);

        }
        else
        {
            un(a, b + n);
            un(b, a + n);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++)
    {
        if(fa[i] == i)
            ans++;
    }
    cout << ans;
    return 0;
}
2022/7/20 19:49
加载中...