我的代码有个奇怪的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;
}