人人都是好朋友

鏈接：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;
}