#3 求助
查看原帖
#3 求助
244051
hsk花生壳楼主2022/1/22 16:03

我的代码有个奇怪的bug,将第78行代码取消注释后可以AC,但是注释起来就会在#3最后一组数据出错(不知道让不让放测试点数据)

这块代码需要更新两次(进行两次anc)才能得出正确询问,有没有大佬帮忙看看我的并查集是不是有问题?十分感谢!

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
using namespace std;
const int N = 1000005;
struct dsu
{
    int dad[N];
    dsu()
    {
        for(int i = 1;i<=N;i++)
        {
            this->dad[i] = i;
        }
    }

    void clear()
    {
        for(int i = 1;i<=N;i++)
        {
            this->dad[i] = i;
        }
    }
    int anc(int a)
    {
        if(dad[a] == a) return dad[a];
        return dad[a] = anc(dad[a]);
    }
    bool ask(int a,int b)
    {
        return anc(a) == anc(b);
    }
    void uni(int a,int b)
    {
        a = anc(a);
        b = anc(b);
        dad[a] = b;
    }
};

int n;
int r[N][3];
dsu d;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        bool flag = 1;
        vector <int> p;
        map <int,int> m;
        
        cin>>n;
        d.clear();
        memset(r,0,sizeof(r));
        for(int i = 1;i<=n;i++)
        {
            cin>>r[i][0]>>r[i][1]>>r[i][2];
            p.push_back(r[i][0]);
            p.push_back(r[i][1]);
        }
        sort(p.begin(),p.end());
        p.erase(unique(p.begin(),p.end()),p.end());
        for(int i = 0;i<p.size();i++) 
        {
            m[p[i]] = i;
        }
        for(int i = 1;i<=n;i++)
        {
            if(r[i][2] == 1)
                d.uni(m[r[i][0]],m[r[i][1]]);
        }
        for(int i = 1;i<=n;i++)
        {
            //d.ask(m[r[i][0]],m[r[i][1]]);
            if(r[i][2] == 0 && d.ask(m[r[i][0]],m[r[i][1]]))
            {
                flag = 0;
                break;
            }
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}
2022/1/22 16:03
加载中...