Luogu P1955 程序自动分析

Luogu P1955 程序自动分析

核心思路：并查集+离散化。

然而离散化打错还检查不出来的我是不是没救了

#include<bits/stdc++.h>
#define N 100010

int t,n,siz;
int a[N*2],b[N*2],fa[N*2]; //a--discrete->t
bool ans;

struct node {
	int i,j,e;
};

node input[N];

namespace WalkerV {
	void Init() {
		memset(input,0,sizeof(input));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(fa,0,sizeof(fa));
		return;
	}

	void Read() {
		scanf("%d",&n);
		for(int k=1;k<=n;k++) {
			scanf("%d%d%d",&input[k].i,&input[k].j,&input[k].e);
			a[k*2-1]=input[k].i,a[k*2]=input[k].j;
		}
		return;
	}

	void Discrete() {
		std::sort(a+1,a+n*2+1);
		for(int k=1;k<=n*2;k++) {
			b[k]=a[k];
		}
		siz=std::unique(b+1,b+n*2+1)-(b+1);
		return;
	}

	int Query(int x) {
		return std::lower_bound(b+1,b+siz+1,x)-b;
	}

	bool Compare(node x,node y) {
		return x.e>y.e;
	}

	int Find(int x) {
		return fa[x]==x?x:fa[x]=Find(fa[x]);
	}
	
	void Merge(int x,int y) {
		fa[Find(y)]=Find(x);
		return;
	}

	void Solve() {
		Discrete();
		for(int k=1;k<=siz;k++) {
			fa[k]=k;
		}
		std::sort(input+1,input+n+1,Compare);
		for(int k=1;k<=n;k++) {
			if(input[k].e) {
				Merge(Query(input[k].i),Query(input[k].j));
			}
			else {
				if(Find(Query(input[k].i))==Find(Query(input[k].j))) {
					ans=false;
					return;
				}
			}
		}
		ans=true;
		return;
	}

	void Print() {
		printf("%s
",ans?"YES":"NO");
		return;
	}
}

int main()
{
	scanf("%d",&t); 
	for(int k=1;k<=t;k++) {
		WalkerV::Init();
		WalkerV::Read();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}