国内最大设计网站,互推商盟,wordpress连接信息,网络公司电话Luogu 写个并查集来维护就行了。先合并所有相等的变量#xff0c;如果有两个不相等的变量相等#xff0c;那么就输出NO。注意得先合并所有相等的变量#xff0c;再来判断。因为如果两个操作一起搞的话#xff0c;可能会有两个变量在某次查询的时候不相等#xff0c;但后面…Luogu 写个并查集来维护就行了。先合并所有相等的变量如果有两个不相等的变量相等那么就输出NO。注意得先合并所有相等的变量再来判断。因为如果两个操作一起搞的话可能会有两个变量在某次查询的时候不相等但后面被合并了。还有就是\(i,j\)贼jb大要离散化一下。 #include bits/stdc.hconst int max_n1e55;int T,N,tot;
int father[max_n1],num[max_n1],A[max_n1],X[max_n],Y[max_n],Z[max_n];inline int read()
{register int x0;register char chgetchar();while(!isdigit(ch))chgetchar();while(isdigit(ch)){x(x1)(x3)ch-0;chgetchar();}return x;
}int find_father(int x)
{return (father[x]x)?x:father[x]find_father(father[x]);
}void merge(int x,int y)
{father[find_father(x)]find_father(y);
}bool is_same(int x,int y)
{return find_father(x)find_father(y);
} int main()
{int flag;Tread();while(T--){flagtot0;Nread();for(int i1;iN;i){X[i]read(),Y[i]read(),Z[i]read();num[i]X[i],num[iN]Y[i];}std::sort(num[1],num[(N1)1]);for(int i1;iN1;i)if(num[i]^num[i-1]) A[tot]num[i];for(int i1;itot;i) father[i]i;for(int i1;iN;i)if(Z[i]) merge(std::lower_bound(A[1],A[1tot],X[i])-A,std::lower_bound(A[1],A[1tot],Y[i])-A);for(int i1;iN;i){if(!Z[i] is_same(std::lower_bound(A[1],A[1tot],X[i])-A,std::lower_bound(A[1],A[1tot],Y[i])-A)){puts(NO);flag1;break;}}if(!flag) puts(YES);}return 0;
} 转载于:https://www.cnblogs.com/zcdhj/p/8401388.html
