并查集是错解吗?悬一关
查看原帖
并查集是错解吗?悬一关
669171
z_yq楼主2024/6/1 11:38

求调,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分,三色猜想

2024/6/1 11:38
加载中...