Rt,代码如下:
// Problem : 【数据删除】
// Contest : UOJ - 【数据删除】
// URL : http://【数据删除】/contest/292/problem/337
// Memory Limit : 1024 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <algorithm>
#include <iostream>
#include <map>
#pragma GCC operize( 2 )
using namespace std;
int fa[ 200010 ];
void init( int n )
{
for ( int i = 0; i <= n; i++ )
fa[ i ] = i;
}
int find( int x )
{
if ( fa[ x ] == x )
return x;
return fa[ x ] = find( fa[ x ] );
}
bool query( int x, int y )
{
return ( find( x ) == find( y ) );
}
void merge( int x, int y )
{
x = find( x );
y = find( y );
fa[ x ] = y;
}
int lsh( int x, int ls[], int n )
{
return lower_bound( ls, ls + n, x ) - ls;
}
int main()
{
int t;
cin >> t;
while ( t-- )
{
int n;
cin >> n;
bool flag = true;
int x[ 100010 ], y[ 100010 ], opt[ 100010 ];
int ls[ 200020 ];
int cnt = 0;
bool pfq0 = 1, pfq1 = 1;
for ( int i = 0; i < n; i++ )
{
cin >> x[ i ] >> y[ i ] >> opt[ i ];
ls[ cnt++ ] = x[ i ];
ls[ cnt++ ] = y[ i ];
}
sort( ls, ls + cnt );
int len = ls + cnt - unique( ls, ls + cnt );
init( len + 10 );
for ( int i = 0; i < n; i++ )
{
if ( opt[ i ] )
merge( lsh( x[ i ], ls, len ), lsh( y[ i ], ls, len ) );
}
for ( int i = 0; i < n; i++ )
{
if ( !opt[ i ] )
{
if ( query( lsh( x[ i ], ls, len ), lsh( y[ i ], ls, len ) ) )
{
flag = false;
break;
}
}
}
if ( flag )
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
}
}