Cod sursa(job #3213642)

Utilizator alexandraiacobelAlexandra Iacob alexandraiacobel Data 13 martie 2024 12:25:54
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
const int Nmax=100005;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int father[Nmax],i,j,m,n;
int findroot(int x)
{
    if(father[x] < 0 )
        return x; //returnez tatal si din el voi face father[x]
            //as putea returna si father[x] kinda
    father[x] = findroot(father[x]);
     return father[x];

}

void unire(int x, int y)
{
    int r_x = findroot(x);
    int r_y = findroot(y);

    if(r_x == r_y)
        return;

    if( father[r_x] > father[r_y])    //Check la nr de componente   //eu vr in r_x sa fie ala mai mare
    {
        swap(r_x, r_y);
    }
    father[r_x]+=father[r_y]; // r_x devine radacina mondiala

    father[r_y] = r_x; //il  atasez pe r_x(ala mai mic) la r_y;

}
int main()
{
    fin>>n>>m;

    for(i=1; i<=n; i++)
        father[i] = -1;// initializare. 1 sg comp

    for(i=1; i<=m; i++)
    {
        int c,x,y;
        fin>>c>>x>>y;

        if(c==1)
            unire(x,y);
        else
        {
            if(findroot(x) == findroot(y))
            {
                fout<<"DA\n";
            }
            else
                fout<<"NU\n";
        }
    }

    return 0;
}