学计算机网站开发好吗,标书制作代做公司,网站建设中页面html,网站制作价格东莞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
