NOI2015 洛谷P1955 程序自动分析（并查集+离散化）

这可能是我目前做过的最简单的一道noi题目了……

先对e=1的处理，用并查集；再对e=0查询，如果这两个在同一集合中，则为“”NO“，最后都满足的话输出”“YES”；

数值很大，用一下离散化就行了。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e6+10;
 4 int t,n,fa[N],b[N*3];
 5 struct node{
 6     int x,y,e;
 7 }a[N];
 8 bool cmp(node a,node b){//e=1的放在前面 
 9     return a.e>b.e;
10 }
11 int get(int x){
12     return fa[x]==x?fa[x]:fa[x]=get(fa[x]);
13 }
14 int main(){
15     scanf("%d",&t);
16     while(t--){
17         int tot=0;
18         memset(b,0,sizeof(b));
19         memset(a,0,sizeof(a));
20         memset(fa,0,sizeof(fa));
21         int vis=1;
22         scanf("%d",&n);
23         for(int i=1;i<=n;i++){
24             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].e);
25             b[++tot]=a[i].x;b[++tot]=a[i].y;
26         }
27         sort(b+1,b+tot+1);
28         int cnt=unique(b+1,b+tot+1)-b-1;
29         for(int i=1;i<=n;i++){
30             a[i].x=lower_bound(b+1,b+cnt+1,a[i].x)-b;
31             a[i].y=lower_bound(b+1,b+cnt+1,a[i].y)-b;
32         }
33         for(int i=1;i<=cnt;i++) fa[i]=i;
34         sort(a+1,a+n+1,cmp);
35         for(int i=1;i<=n;i++){
36             int r1=get(a[i].x);
37             int r2=get(a[i].y);
38             if(a[i].e){
39                 fa[r1]=r2;
40             }
41             else if(r1==r2){
42                 cout<<"NO"<<endl;
43                 vis=0;
44                 break;
45             }
46         }
47         if(vis) cout<<"YES"<<endl;
48     }
49 }