Cod sursa(job #1913349)

Utilizator andrei232000Andrei Maria andrei232000 Data 8 martie 2017 12:38:17
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("disjoint.in");
ofstream fout("disjoint.out");
int t[100002], r[100002];
int N, M, i, x, y, z;
int gaseste(int e)
{
    if(t[e])
    {
        e = gaseste(t[e]);
    }
    return e;
}
void verifica(int u, int v)
{
    if(gaseste(u) == gaseste(v))
    {
        fout<<"DA"<<'\n';
    }
    else
    {
        fout<<"NU"<<'\n';
    }
}
void uneste(int u, int v)
{
    u = gaseste(u);
    v = gaseste(v);
    if(r[u] < r[v])
    {
        t[u] = v;
    }
    else if(r[u] > r[v])
    {
        t[v] = u;
    }
    else
    {
        t[u] = v;
        ++r[v];
    }
}
int main()
{
    fin>>N>>M;
    for(i = 0; i < M; ++i)
    {
        fin>>z;
        fin>>x>>y;
        if(z&1)
        {
            uneste(x, y);
        }
        else
        {
            verifica(x, y);
        }
    }
    return 0;
}