人人都是好朋友
时间限制：2秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
牛可乐作为三军统帅，是要时时刻刻关照着下属的。
现在牛可乐想要知道自己的手下之间的友好关系，所以他收集了n nn张纸条，上面写着三个整数a i , b i , c i a_i,b_i,c_iai,bi,ci，表示如果c i c_ici为1 11，表示手下a i a_iai和手下b i b_ibi是朋友，反之则是敌人。
牛可乐想要知道这些信息有没有互相矛盾的地方，可是这个问题太难了，只好来问你了
如果A与B友好，B又与C友好，那么A与C也是友好的。
如果两个人既是友好的又是不友好的则视为相互矛盾的。
牛可乐的手下有 1e9 个。
输入描述：
输入第一行给出一个正整数T TT，表示测试案例的数量。
对于每个测试用例.第一行给出一个正整数n nn，表示有n nn个友好关系
接下来每n nn行给出三个正整数a i , b i , c i a_i,b_i,c_iai,bi,ci，表示手下a i a_iai和手下b i b_ibi之间的友好关系.
输出描述：
每组案例输出一行，若这些关系没有矛盾，输出 "Y E S YESYES”，否则输出 “N O NONO”
示例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 ≤ T ≤ 10 1≤T≤101≤T≤10
1 ≤ n ≤ 1 e 6 1≤n≤1e61≤n≤1e6
1≤a,b≤1e9
c∈{0,1}
对于每组样例，保证 ∑n≤1010000
建议使用 scanf 读入
解题思路
首先因手下编号达1 e 9 1e91e9，需对所有出现的a i 、 b i a_i、b_iai、bi进行离散化（收集所有编号存入数组，排序并去重，将大数映射为小索引）；随后初始化并查集，先处理所有c i = 1 c_i=1ci=1的友好关系，通过并查集合并对应编号的映射索引，维护友好关系的传递性；接着遍历所有c i = 0 c_i=0ci=0的敌对关系，查找对应编号的映射索引在并查集中的根节点，若根节点相同则说明两人既是朋友又是敌人，存在矛盾，输出N O NONO；若所有敌对关系的映射索引根节点均不同，输出Y E S YESYES；该方法通过离散化解决大数编号问题，结合并查集高效维护友好关系，时间复杂度适配n nn达1 e 6 1e61e6、∑ n ≤ 1 e 7 ∑n≤1e7∑n≤1e7的规模，精准判断关系是否矛盾。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=2e6+10;ll fa[N],v[N];structnode{ll x,y,z;}a[N];llget(ll x){if(x==fa[x])returnx;returnfa[x]=get(fa[x]);}voidsolve(){ll n;cin>>n;ll p=0,p1=0;for(ll i=1;i<=n;i++){cin>>a[i].x>>a[i].y>>a[i].z;v[++p]=a[i].x;v[++p]=a[i].y;}sort(v+1,v+1+p);for(ll i=1;i<=p;i++){if(v[i]!=v[p1])v[++p1]=v[i];}for(ll i=1;i<=p1;i++)fa[i]=i;for(ll i=1;i<=n;i++){if(!a[i].z)continue;ll aa=lower_bound(v+1,v+1+p1,a[i].x)-v;ll bb=lower_bound(v+1,v+1+p1,a[i].y)-v;ll x=get(aa),y=get(bb);fa[x]=y;}boolf=1;for(ll i=1;i<=n;i++){if(a[i].z)continue;ll aa=lower_bound(v+1,v+1+p1,a[i].x)-v;ll bb=lower_bound(v+1,v+1+p1,a[i].y)-v;ll x=get(aa),y=get(bb);if(x==y){f=0;break;}}if(f)cout<<"YES\n";elsecout<<"NO\n";}intmain(){ll t;cin>>t;while(t--)solve();return0;}
