Pagini recente » Monitorul de evaluare | Cod sursa (job #362822) | Cod sursa (job #1884580) | Cod sursa (job #3038001) | Cod sursa (job #447487)
Cod sursa(job #447487)
/*
* File: main.cpp
* Author: virtualdemon
*
* Created on April 28, 2010, 8:56 PM
*/
#include <cstdlib>
#include <fstream>
#define Nmax 100011
/*
*
*/
using namespace std;
int f[Nmax], r[Nmax];
inline int find( int x )
{
int y, z;
for( y=x; y != f[y]; y=f[y] );
for( ; x != f[x]; )
{
z=f[x];
f[x]=y;
x=z;
}
return y;
}
inline void Unite( int x, int y )
{
if( r[x] == r[y] )
{
if( x != y )
f[y]=x;
++r[y];
}
else r[x]=r[y]=min( r[x], r[y] );
}
int main(int argc, char** argv)
{
int N, M, i, j, k;
ifstream in( "disjoint.in" );
ofstream out( "disjoint.out" );
in>>N>>M;
for( i=1; i <= N; ++i )
f[i]=i, r[i]=1;
for( ; M; --M )
{
in>>i>>j>>k;
if( 1 == i )
{
Unite( find(j), find(k) );
}
else {
if( find(j) == find(k) )
out<<"DA\n";
else out<<"NU\n";
}
}
return (EXIT_SUCCESS);
}