Cod sursa(job #2280649)

Utilizator IordachescuAncaFMI Iordachescu Anca Mihaela IordachescuAnca Data 10 noiembrie 2018 22:34:48
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include<fstream>
#define NMAX 100003

using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");

int p[NMAX], rang[NMAX], n, m, i, a, b, c;

int root(int x)
{
    while ( p[x] != x)
    {
        x = p[x];
    }
    return x;
}

int verify(int x, int y)
{
    int i = root(x);
    int j = root(y);
    if (i == j)
    {
        return 1;
    }
    return 0;
}

void unionn(int x, int y)
{
    int i = root(x);
    int j = root(y);
    if (rang[i] > rang[j])
    {
        p[j] = i;
    }
    if (rang[i] < rang[j])
    {
        p[i] = j;
    }
    if (rang[i] == rang[j])
    {
        p[j] = i;
        rang[i] ++;
    }
}
int main()
{
    fin >> n >> m;
    for (i = 1; i <= n; i ++)
    {
        p[i] = i;
        rang[i] = 0;
    }
    for (i = 1; i <= m;i ++)
    {
        fin >> a >> b >> c;
        if(a == 1 )
        {
            unionn(b,c);
        }
        else
        {
            if (verify(b,c) == 1)
            {
                fout << "DA" << "\n";
            }
            else
            {
                fout << "NU" << "\n";
            }
        }
    }

    fin.close();
    fout.close();

    return 0;
}