题目链接

https://ac.nowcoder.com/acm/problem/204870

题目大意

t组数据输入，n个关系，每个关系包括三个数a，b两个人，c=1表示二者互为好朋友，c=0表示二者互为敌人，遵循朋友的朋友就是朋友的原则，问这组数据是否自相矛盾，（如果两个人既是友好的又是不友好的则视为相互矛盾的），不矛盾输出YES，矛盾输出NO。

题目分析

一打眼过去，并查集吧。因为有“朋友的朋友就是朋友”，显然是连通区域。
（不会并查集的可以看一下 并查集例题及讲解链接 ）
并查集有了，但是发现总人数是1e9个人，实际给出的关系只有1e6个，这就说明…………要离散化！
如何离散化呢？
对我这种小白来说感觉好巧妙，但是大佬的题解都是一笔带过。

//离散化核心代码
//-----------------------------------------
for(int i=1;i<=n;i++){
    cin>>a[i]>>b[i]>>c[i];
}
for(int i=1;i<=n;i++){
    d[++cnt]=a[i];
    d[++cnt]=b[i];
}
sort(d+1,d+1+cnt);
cnt=unique(d+1,d+1+cnt)-d;
for(int i=1;i<=n;i++){
    a[i]=lower_bound(d+1,d+cnt+1,a[i])-d;
    b[i]=lower_bound(d+1,d+cnt+1,b[i])-d;
}
//-----------------------------------------

离散化过程讲解：
S1：先把a，b，c存储在数组里；
S2：（重新回忆一下a，b分别代表什么？两个人的序号吧）因为a，b所涉及到的人才是我们应该去关心的，而剩下的人（最少剩下1e9-2*1e6人）是我们不关心的，因此离散化是显而易见的，我们就把a，b涉及到的人都存储到一个d数组中；
S3：将d数组从小到大排序，利用unique函数除重，算出涉及到的总人数；
S4：最后通过lower_bound函数为每个人重新分配序号，（按照每个人原序号的相对大小关系排序，原序号所对应位置的索引就是新序号）从而实现了离散化。
ps： unique函数基础讲解

离散化完成之后，进行fa数组的初始化，开始构建连通区域。
遍历所有的c，若c=1，那么构建连通区域；
再遍历所有的c，若c!=1，那么判断一下，若此时对应的a和b对应的连通区域相同，wrong标志置一，表示矛盾了；反之wrong表示不变为0，表示不矛盾。

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
const int M=2*N;
int fa[M], d[M];
int a[N], b[N], c[N];
int find(int x){//太简洁了，实现了find操作，而且还进行了路径压缩
    return fa[x]==x?x:fa[x]=find(fa[x]);
}
int main(){
    int t,n,cnt;
    cin>>t;
    while(t--){
        cnt=0;
        cin>>n;
//-------------------------离散化----------------------------------
        for(int i=1;i<=n;i++){
            cin>>a[i]>>b[i]>>c[i];
        }
        for(int i=1;i<=n;i++){
            d[++cnt]=a[i];
            d[++cnt]=b[i];
        }
        sort(d+1,d+1+cnt);
        cnt=unique(d+1,d+1+cnt)-d;
        for(int i=1;i<=n;i++){
            a[i]=lower_bound(d+1,d+cnt+1,a[i])-d;
            b[i]=lower_bound(d+1,d+cnt+1,b[i])-d;
        }
//-----------------------------------------------------------------

//-------------------------初始化----------------------------------
        for(int i=1;i<=cnt;i++){
            fa[i]=i;
        }
//-----------------------------------------------------------------

//-------------------------判断-------------------------------------
        for(int i=1;i<=n;i++){
            if(c[i]==1){
                int rx=find(a[i]),ry=find(b[i]);
                if(rx!=ry)
                    fa[rx]=ry;
            }
        }
        int w=0;
        for(int i=1;i<=n;i++){
            if(c[i]!=1){
                if(find(a[i])==find(b[i])) w=1;
            }
        }
//----------------------------------------------------------------

//-------------------------输出------------------------------------
        cout<<(w==1?"NO":"YES")<<endl;
    }
}

总结

挺难的，离散化不会，并查集用的也不熟。最后c的判断也挺巧妙。
过一阵写一下离散化，出份题解。
最后的最后我还想再问一句：我什么时候才能成为大佬啊啊啊！！！