链接：https://ac.nowcoder.com/acm/contest/5158/H
来源：牛客网
人人都是好朋友
时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
牛可乐作为三军统帅，是要时时刻刻关照着下属的。
现在牛可乐想要知道自己的手下之间的友好关系，所以他收集了 nn 张纸条，上面写着三个整数 a_i,b_i,c_ia
i
,b
i
,c
i
，表示如果 c_ic
i
为 11，表示手下 a_ia
i
和手下 b_i b i
是朋友，反之则是敌人。
牛可乐想要知道这些信息有没有互相矛盾的地方，可是这个问题太难了，只好来问你了
如果 A 与 B 友好，B 又与 C 友好，那么 A 与 C 也是友好的。
如果两个人既是友好的又是不友好的则视为相互矛盾的。
牛可乐的手下有 1e9 个。
输入描述:
输入第一行给出一个正整数 TT，表示测试案例的数量。
对于每个测试用例.第一行给出一个正整数 nn，表示有 nn 个友好关系
接下来每 nn 行给出三个正整数 a_i,b_i,c_ia
i
,b
i
,c
i
，表示手下 a_ia
i
和手下 b_ib
i
之间的友好关系.
输出描述:
每组案例输出一行，若这些关系没有矛盾，输出 "YES”，否则输出 “NO”
示例1
输入
复制
2
3
1 2 1
1 3 1
2 3 1
3
1 2 1
1 3 1
2 3 0
输出
复制
YES
NO
备注:
1\leq T\leq 101≤T≤10
1\leq n\leq 1e61≤n≤1e6
1 \leq a,b \leq 1e91≤a,b≤1e9
c\in{0,1}c∈{0,1}
对于每组样例，保证 \sum n \leq 1010000∑n≤1010000
建议使用 scanf 读入。
分析一下这道题，很明显就要用并查集判断是不是属于一个朋友圈。
我们用一个结构体存下ai,bi,ci;按照ci降序排序。这是因为我们首先将是朋友的人弄成一个个朋友圈，然后在去判断不是朋友的人如果在一个朋友圈那么就矛盾了。并查集的三个重要操作，
1.初始化：开始的时候每一个元素的祖先都是自己，也就是说，自己就是一个朋友圈。
for(int i=0;i<n;i++)
father[i]=i;
2.查找自己的祖先：也就是查看自己属于哪一个朋友圈,我们可以递归查询，但是如果树的深度较大，查询会很耗时，那么我们就在查询的时候，顺便修改沿途上的结点的祖先。
之后就是并查集的强项，搜索了，并查集的搜索很巧妙，用到一个叫路径压缩的思想，抽象树的所要子孙节点都指向了根节点。
int getfather(int d){
if(d==father[d])
return d;
else
return father[d]=getfather(father[d]);
}
3.合并两个结点的关系，也就是说a,b属于同一个朋友圈，那么我们就把a的祖先改为b的祖先，或者b改为a的。就很简单了。当然改之前我们需要查找到其祖先
void unionSet(int a,int b)
{
int fathera=getfather[a];
int fatherb=gerfather[b];
father[fathera]=fatherb;
//假如father[3]=4;father[5]=7;father[4]=7;
}
也就是说father[3]的最上级原本是4，现在，最上级是7了，也就是说将 father[3]合并到father[5]这个树里面去了。
由于此题数据较大，我们如果不离散化，那么数组就需要开很大，不方便，那么我们就离散化减小他们的大小，但是相对大小不改变。
还需要去重。因为关系比较复杂。元素之间肯定有重的。
离散化的重要操作是借助lower_bound函数来求得其在数组的相对位置，那么就是其相对大小，这题我们不考虑其实际大小。
int c = unique(unequal,unequal+tot) - unequal;//去重
//给每个元素从大到小编号
for(int i=0; i<n; i++){
a[i].x = lower_bound(unequal, unequal+c, a[i].x)-unequal;
a[i].y = lower_bound(unequal, unequal+c, a[i].y)-unequal;
}
最后在e为0的时候就开始判断是不是在一个朋友圈，如果是就表示矛盾了。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll unequal[2000010];
int u[1000010];
struct node{
ll x, y, e;
}a[1000010];
bool cmp(node a, node b){
return a.e>b.e;
}
//递归缩短路径
int get(int a){
if(u[a]==a) return a;
return u[a] = get(u[a]);
}
int main(){
int t;
scanf("%d", &t);
while(t--){
int n, tot=0;
scanf("%d", &n);
for(int i=0; i<n; i++){
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].e);
unequal[tot++] = a[i].x;
unequal[tot++] = a[i].y;
}
sort(unequal, unequal+tot);
//统计去重后的元素个数
int c = unique(unequal,unequal+tot) - unequal;
//给每个元素从大到小编号
for(int i=0; i<n; i++){
a[i].x = lower_bound(unequal, unequal+c, a[i].x)-unequal;
a[i].y = lower_bound(unequal, unequal+c, a[i].y)-unequal;
}
sort(a, a+n, cmp);
for(int i=0; i<c; i++)
u[i] = i;
int flag=1;
for(int i=0; i<n; i++){
int dy = get(a[i].y);
int dx = get(a[i].x);
if(a[i].e){
u[dx] = dy;
}
else{
if(u[dx]==u[dy]){
flag=0;
printf("NO\n");
break;
}
}
}
if(flag)
printf("YES\n");
}
return 0;
}
