这是补更帖。。。
uoj127/bzoj4195
1 //两种操作分开处理！！！我是艾斯比 2 #include<stdio.h> 3 #include<algorithm> 4 using namespace std; 5 6 #define maxn 1000005 7 struct node{ 8 int u,v; 9 }con[maxn],un[maxn]; 10 int cc,uu,T,n,cnt,father[maxn<<1],hash[maxn<<1]; 11 12 int getf(int x){ 13 return father[x]=father[x]==x?x:getf(father[x]); 14 } 15 bool kruskal(){ 16 for(int i=1;i<=cc;i++){ 17 int u=lower_bound(hash+1,hash+1+cnt,con[i].u)-hash; 18 int v=lower_bound(hash+1,hash+1+cnt,con[i].v)-hash; 19 int fa=getf(u); 20 int fb=getf(v); 21 if(fa!=fb)father[fa]=fb; 22 } 23 for(int i=1;i<=uu;i++){ 24 int u=lower_bound(hash+1,hash+1+cnt,un[i].u)-hash; 25 int v=lower_bound(hash+1,hash+1+cnt,un[i].v)-hash; 26 int fa=getf(u); 27 int fb=getf(v); 28 if(fa==fb)return false; 29 } 30 return true; 31 } 32 int main(){ 33 freopen("1.in","r",stdin); 34 scanf("%d",&T); 35 while(T--){ 36 scanf("%d",&n); 37 cnt=cc=uu=0; 38 for(int i=1;i<=n;i++){ 39 int a,b,c; 40 scanf("%d%d%d",&a,&b,&c); 41 if(c==1){ 42 con[++cc].u=a; 43 con[cc].v=b; 44 } 45 else{ 46 un[++uu].u=a; 47 un[uu].v=b; 48 } 49 hash[++cnt]=a; 50 hash[++cnt]=b; 51 } 52 sort(hash+1,hash+1+cnt); 53 cnt=unique(hash+1,hash+1+cnt)-(hash+1); 54 for(int i=1;i<=cnt;i++)father[i]=i; 55 if(kruskal())printf("YES "); 56 else printf("NO "); 57 } 58 return 0; 59 }
注释实为肺腑之言