Pagini recente » Cod sursa (job #359639) | Cod sursa (job #1337495) | Cod sursa (job #1939050) | Cod sursa (job #2037885) | Cod sursa (job #2225178)
#include <fstream>
#define dim 100005
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");
int rg[dim], t[dim];
int n, m, caz, x, y;
int find (int x)
{
int R , y;
for ( R = x ; t[R] != R ; R = t[R] );
for( ;t[x] != x ; )
{
y = t[x];
t[x] = R;
x = y;
}
return R;
}
void unite( int x, int y)
{
if( rg[x] > rg[y] )
t[y] = x;
else
t[x] = y;
if( rg[x] == rg[y] )
rg[y]++;
}
int main()
{
f >> n >> m;
for( int i = 1 ; i <= n ; i++ )
t[i]= i, rg[i] = 1;
while( m-- )
{
f >> caz >> x >> y;
if ( caz == 2)
{
if( find(x) == find(y) )
g << "Da\n";
else
g << "Nu\n";
}
else
unite(find(x), find (y));
}
return 0;
}