Cod sursa(job #2792081)

Utilizator AndreibatmanAndrei Croitoriu Andreibatman Data 31 octombrie 2021 20:36:24
Problema Paduri de multimi disjuncte Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.62 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int n,m,r[100010],op,a,b,i;
int cauta(int x)
{
    if(x!=r[x])
        r[x]=cauta(r[x]);
    return r[x];
}
void unire(int a,int b)
{
    int rx=cauta(a);
    int ry=cauta(b);
    r[rx]=ry;
}
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
        r[i]=i;
    for(i=1;i<=m;i++)
    {
        fin>>op>>a>>b;
        if(op==2)
        {
            if(cauta(a)==cauta(b))
                fout<<"Da\n";
            else fout<<"Nu\n";
        }
        else unire(a,b);
    }
    return 0;
}