Cod sursa(job #2225176)

Utilizator tiberiu392Tiberiu Ungurianu tiberiu392 Data 26 iulie 2018 11:46:41
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#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;
}