Cod sursa(job #269089)

Utilizator raula_sanChis Raoul raula_san Data 2 martie 2009 13:22:41
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <cstdio>
#define MAX_N 100001

int T[MAX_N], R[MAX_N];
int N, M;

void Set()
{
     int i;
     for ( i = 1; i <= N; ++i )
     {
         T[i] = i;
         R[i] = 1;
     }
}

int Parinte(int n)
{
    int x = n;
    while(T[x] != x)
               x = T[x];
    while(T[n] != n)
    {
               int y = T[n];
               T[n] = x;
               n = y;
    }
    return x;
}

int main()
{
    freopen("disjoint.in", "rt", stdin);
    freopen("disjoint.out", "wt", stdout);
    
    int i, x, y, c;
    for ( scanf("%d %d", &N, &M), Set(), i = 1; i <= M; ++i )
    {
        scanf("%d %d %d", &c, &x, &y);
        
        // reuniune
        if(c == 1)
        {
             int t, s;
             t = Parinte(x);
             s = Parinte(y);
             
             if(R[t] < R[s])
                     T[t] = s;
             else
                 T[s] = t;
                 
             if(R[t] == R[s])
                     ++ R[t];
        }
        // interogare
        else
        {
            int t, s;
            t = Parinte(x);
            s = Parinte(y);
            
            if(t == s)
                 printf("DA\n");
            else
                printf("NU\n");
        }
    }
    
    fclose(stdin);
    fclose(stdout);
    return 0;
}