Cod sursa(job #3212499)

Utilizator FlaviuuuFlaviu Flaviuuu Data 11 martie 2024 20:13:37
Problema Paduri de multimi disjuncte Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int par[100000], sz[100000], op;
unsigned long long s;
int n, m, a, b;
int getpar(int a)
{
    if(par[a] == 0)
    {
        par[a] = a;
        return a;
    }
    while(a!=par[a])
        a=par[a];
    return a;
}
void connect(int a,int b)
{
    a=getpar(a);
    b=getpar(b);
    if(a!=b)
    {
        if(sz[a]<sz[b])
            swap(a,b);
        par[b]=a;
        par[b]=a;
        sz[a]+=sz[b];
    }
}
int main()
{
    fin>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        fin>>op>>a>>b;
        if(op == 1)
        {
            connect(a, b);
        }
        if(op == 2)
        {
            if(getpar(a) == getpar(b))
                fout<<"DA";
            else
                fout<<"NU";
            fout<<'\n';
        }
    }
    return 0;
}