Cod sursa(job #2947918)

Utilizator alexutzIstrate Cristian Alexandru alexutz Data 26 noiembrie 2022 21:46:49
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <fstream>

using namespace std;

ifstream f("disjoint.in");
ofstream g("disjoint.out");


int n,m;
int inaltime[100001];
int tata[100001];


int reprez(int x)
{
   if(tata[x] == 0)
        return x;
   tata[x] = reprez(tata[x]);
   return tata[x];
}


void reuniune(int reprezx,int reprezy)
{
    if(inaltime[reprezx] > inaltime[reprezy])
        tata[reprezy] = reprezx;
    else
    {
        tata[reprezx] = reprezy;
        if(inaltime[reprezx] == inaltime[reprezy])
            inaltime[reprezy]++;
    }


}


int main()
{
    f >> n >> m;
    int i,op,x,y;
    int repx,repy;
    for(i=1;i<=m;i++)
    {
        f >> op >> x >> y;
        repx = reprez(x);
        repy = reprez(y);
        if(op == 1)
        {
            if(repx != repy)
                reuniune(repx,repy);
        }
        else
            {
                if(repx == repy)
                    g << "DA\n";
                else
                    g << "NU\n";
            }

    }





}