判断好朋友（并查集离线操作+离散化）

链接：https://ac.nowcoder.com/acm/contest/5158/H
来源：牛客网

牛可乐作为三军统帅，是要时时刻刻关照着下属的。

现在牛可乐想要知道自己的手下之间的友好关系，所以他收集了

牛可乐想要知道这些信息有没有互相矛盾的地方，可是这个问题太难了，只好来问你了

如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的。

如果两个人既是友好的又是不友好的则视为相互矛盾的。

牛可乐的手下有 1e9 个。

输入描述:

输入第一行给出一个正整数

对于每个测试用例.第一行给出一个正整数

接下来每

输出描述:

每组案例输出一行，若这些关系没有矛盾，输出 "YES”，否则输出 “NO”

链接：https://ac.nowcoder.com/acm/contest/5158/H
来源：牛客网

输入

复制

输出

复制

YES
NO

备注:

1\leqT\leq10

对于每组样例，保证

建议使用 scanf 读入

一眼看过去肯定要用并查集的

1.但是a,b是小于等于1e9的所以要进行离散化，因为n是小于1e6的

2.要判断是不是有矛盾，你可以先加入ci==1的就是先让朋友连成一个并查集，然后在判断ci==0的两个节点是不是连在了一起（是不是

朋友)

这是关键：

for(int i=1;i<=n;i++){
            if(a[i].ci==1){
                marge(a[i].ai,a[i].bi);
            }
        }
        for(int i=1;i<=n;i++){
            if(a[i].ci==0){
                int u=find(a[i].ai);
                int v=find(a[i].bi);
                if(v==u){
                    flag=0;
                    break;
                }
            }
        }

#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5e6+1000;
struct node{
    int ai;
    int bi;
    int ci;
}a[maxn];
bool cmp(node x,node y){
    return x.ci>y.ci;
} 
int pre[maxn];
int id[maxn];
int r[maxn]; 
int cnt=0;
int n;
void inint(){
    sort(id+1,id+1+cnt);
    cnt=unique(id+1,id+1+cnt)-(id);
    for(int i=1;i<=n;i++){
        a[i].ai=lower_bound(id+1,id+1+cnt,a[i].ai)-(id);
        a[i].bi=lower_bound(id+1,id+1+cnt,a[i].bi)-(id);
    }
} 
int find(int x){
    if(pre[x]==x){
        return x;
    }
    else{
        pre[x]=find(pre[x]);
        return pre[x]; 
    }
}
void marge(int x,int y){
    int t1=find(x);
    int t2=find(y);
    if(t1==t2){
        return ;
    } 
    if(r[t2]>r[t1]){
        pre[t1]=t2;
        r[t2]+=r[t1];
    }
    else{
        pre[t2]=t1;
        r[t1]+=r[t2];
    }
}
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cnt=0;
        for(int i=1;i<=n;i++){
            scanf("%d%d%d",&a[i].ai,&a[i].bi,&a[i].ci);
            id[++cnt]=a[i].ai;
            id[++cnt]=a[i].bi;
        }
        inint();//离散化
        for(int i=0;i<=cnt;i++){
            pre[i]=i;
            r[i]=1;
        } 
        int flag=1;
        for(int i=1;i<=n;i++){
            if(a[i].ci==1){
                marge(a[i].ai,a[i].bi);
            }
        }
        for(int i=1;i<=n;i++){
            if(a[i].ci==0){
                int u=find(a[i].ai);
                int v=find(a[i].bi);
                if(v==u){
                    flag=0;
                    break;
                }
            }
        }
        if(flag){
            printf("YES
");
        } 
        else{
            printf("NO
");
        }
    }
} 
/*
2
3
1 2 1
1 5 1
2 5 1
*/