描述
小Hi给小Ho邮寄了一个天平。收到天平后，小Ho想知道天平在运输过程中是否损坏，为此它准备了A类物品和B类物品共n个（可能只有A类物品，也可能只有B类物品），但无法确定一个物品是哪一类。A类物品的质量都相同，B类物品的质量也相同，但A类物品与B类物品的质量不同。现将n个物品从1到n编号，用天平进行m次测量，每次从n个物品中取i和j两个物品，测量后可以知道物品i和物品j质量是否相同。
现在小Ho想知道能否根据测量结果判定天平是坏的，如果能确定，最早是第几次测量确定的，你能帮帮他吗？
输入
第一行一个数字T，代表数据组数。1<=T<=5。
对于每组数据：
第一行两个整数n，m，分别代表A类、B类物品的总数和测量次数。2<=n<=10000，1<=m<=300000。
接下来m行，每行三个数字x，u，v。x=0代表物品u与物品v质量相等，x=1代表质量不等。
输出
对于每组数据：
若不能确定天平是坏的，则输出一行“great”。
否则，输出两行。
第一行输出“sad”。
第二行输出一个数字p，代表最早第p次测量确定了天平是坏的。
- 样例输入
1
2 2
0 1 2
1 1 2- 样例输出
sad
2
思路：对于每一个物品i，我们可以假设i是R色，则i+n是B色，然后2-sat验证。但是这样的话二分m不方便。我们要在线做。
所以改用并查集来实现：对于每一个关系，如果相同，则合并 u和v，u+n和v+n；否则合并u和v+n，v+u+n，直到出现矛盾。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<string>
const int maxn=;
using namespace std;
int m,n,x,u,v;
int flag=;
int par[maxn],rnk[maxn];
void init( int n )
{
for (int i=;i<=n;i++){
par[i]=i;
rnk[i]=;
}
}
int find( int x )
{
return x==par[x]?x:find(par[x]);
}
void unite( int x, int y )
{
x=find(x);
y=find(y);
if(x==y) return;
if(rnk[x]<rnk[y]) par[x]=y;
else{
par[y]=x;
if (rnk[x]==rnk[y]) rnk[x] ++;
}
}
bool same( int x, int y )
{
return find(x)==find(y);
}
int main()
{
int T;
scanf("%d",&T );
while (T--){
scanf("%d%d",&n,&m );
init(n*+);
flag=;
for(int i=;i<=m;++i){
scanf("%d%d%d",&x,&u,&v );
if (flag){
if(x==){
if(same(u,v+n)){
puts("sad");
printf("%d\n",i);
flag = ;
}
else{
unite(u,v);
unite(v+n,u+n);
}
}
else{
if (same(u,v)||same(u+n,v+n)){
puts("sad");
printf( "%d\n",i);
flag = ;
}
else{
unite(u,v+n);
unite(u+n,v);
}
}
}
}
if (flag) puts("great");
}
return ;
}