Cod sursa(job #825090)
#include <fstream>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int h[100001];
int t[100001];
int n, m;
void Union( int r1, int r2 );
int Find( int x );
int main()
{
fin >> n >> m;
for( int i = 1; i <= n; ++i )
t[i] = i;
int x, y, z, r1, r2;
for( int i = 1; i <= m; ++i )
{
fin >> z >> x >> y;
r1 = Find( x );
r2 = Find( y );
if( z == 1 )
Union( r1, r2 );
else
if( r1 == r2 )
fout << "DA\n";
else
fout << "NU\n";
}
fin.close();
fout.close();
return 0;
}
void Union( int r1, int r2 )
{
if( h[r1] > h[r2] )
t[r2] = r1;
else
{
t[r1] = r2;
if( h[r1] == h[r2] )
h[r2]++;
}
}
int Find( int x )
{
if( t[x] != x )
return t[x] = Find( t[x] );
return x;
}