[acwing 237. program automatic analysis] parallel search + discretization

Topic link

The question ：

Here you are. n A relationship , Every relationship is made up of x,y,st Composed of , When st = 1 I mean x and y equal , When st = 0 Yes means yes x and y It's not equal , Now give you this n A relationship , Ask if these relationships are contradictory .

analysis ：

The equality relation can be regarded as the union of search sets in a set , The unequal relation can be regarded as that the search set is not in a set , Input x and y The upper limit is 1e9, But at most 2e5 Number , Then we can discretize , Because there are no rules on the order , It does not belong to order preserving discretization , So it can be used map To discretize , Here we use unordered_map It will be better than map Much faster , Personal test , Common map Just TLE 了 , But with unordered_map It's over , After discretization, you can make a judgment , We adopt the strategy of looking at equal relations first and then unequal relations , Because this input sequence is actually useless , And there is no error in the equality relation , We can judge the unequal relationship later , See the code below ：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<cstdlib>
#include<climits>
#include<unordered_map>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int mod = 1e9+7;
const int N = 100010;
unordered_map<int,int> mp;
struct node{
    
	int x,y,st;
}g[N];
int pa[N+N];
int find(int x){
    
	if(x != pa[x]) pa[x] = find(pa[x]);
	return pa[x];
}
int main(){
    
	int _;
	cin>>_;
	while(_--){
    
		int n;
		mp.clear();
		scanf("%d",&n);
		int cnt = 0;
		for(int i=1;i<=n;i++){
    
			scanf("%d%d%d",&g[i].x,&g[i].y,&g[i].st);
			if(!mp[g[i].x]) mp[g[i].x] = ++cnt;
			if(!mp[g[i].y]) mp[g[i].y] = ++cnt;
		}
		for(int i=1;i<=cnt;i++) pa[i] = i;
		int flag = 1;
		for(int i=1;i<=n;i++){
    
			int x = mp[g[i].x],y = mp[g[i].y];
			if(g[i].st == 1){
    
				pa[find(x)] = find(y);
			}
		}
		for(int i=1;i<=n;i++){
    
			int x = mp[g[i].x],y = mp[g[i].y];
			if(g[i].st == 0){
    
				if(find(x) == find(y)){
    
					flag = 0;
					break;
				}
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}