求调,rt,并查集难道不能AC?
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e4+9;
ll n,m;
struct node
{
ll lt,rt,ans;
}a[N];
ll fa[3*N],b[3*N],tmp;
inline ll Find(ll x)
{
if(fa[x]==x) return x;
else return fa[x]=Find(fa[x]);
}
int main()
{
ll T;
cin>>T;
while(T--)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>a[i].lt>>a[i].rt>>a[i].ans;
a[i].ans=abs(a[i].ans);
b[++tmp]=a[i].lt;b[++tmp]=a[i].rt;
}
sort(b+1,b+tmp+1);
ll len=unique(b+1,b+tmp+1)-(b+1);
for(int i=1;i<=m;i++)
{
a[i].lt=lower_bound(b+1,b+len+1,a[i].lt-1)-b;
a[i].rt=lower_bound(b+1,b+len+1,a[i].rt)-b;
}
for(int i=1;i<=2*len;i++)
fa[i]=i;
ll f=1;
for(int i=1;i<=m;i++)
{
if(a[i].ans%2==0)
{
if(Find(a[i].lt)==Find(a[i].rt+len) || Find(a[i].lt+len)==Find(a[i].rt))
{
cout<<"false"<<endl;
f=0;
break;
}
fa[Find(a[i].lt)]=Find(a[i].rt);
fa[Find(a[i].lt+len)]=Find(a[i].rt+len);
}
else
{
if(Find(a[i].lt)==Find(a[i].rt) || Find(a[i].lt+len)==Find(a[i].rt+len))
{
f=0;
cout<<"false"<<endl;
break;
}
fa[Find(a[i].lt+len)]=Find(a[i].rt);
fa[Find(a[i].lt)]=Find(a[i].rt+len);
}
}
if(f==1) cout<<"true"<<endl;
}
return 0;
}
代码33分,三色猜想