求助,此题MLE
查看原帖
求助,此题MLE
511271
ダ月Nahida楼主2022/8/17 18:13
#include<bits/stdc++.h>
using namespace std;
int t;
int n;
int tp=0;
int x,y,z;
int a[1000010][2],ts=0;
int f[1000010];
map<int,int> m;
stack<int> st;
int finds(int x){
	return f[x]==x?x:f[x]=finds(f[x]);
}
int main(){
	scanf("%d",&t);
	while(t--){
		ts=0;tp=0;
		for(int i=1;i<=1e6;i++)
			f[i]=i;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d%d%d",&x,&y,&z);
			if(!m[x]){
				m[x]=++tp;
				st.push(x);
			}
			if(!m[y]){
				m[y]=++tp;
				st.push(y);
			}
			if(!z) a[++ts][0]=m[x],a[ts][1]=m[y];
			else{
				int p1=finds(m[x]);
				f[p1]=m[y];
			}
		}
		bool flag=true;
		for(int i=1;i<=ts;i++){
			int p1=finds(m[a[i][0]]),p2=finds(m[a[i][1]]);
			if(p1==p2){
				printf("NO\n");
				flag=false;
				break;
			}
		}
		if(flag) puts("YES");
		while(!st.empty()){
			m[st.top()]=0;
			st.pop();
		}
	}
	return 0;
}
2022/8/17 18:13
加载中...