Cod sursa(job #1363594)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 27 februarie 2015 08:43:34
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include <fstream>
using namespace std;
ifstream f("disjoint.in");
ofstream g("disjoint.out");

int x, y, N, M, tip, GR[100005];

int grupa(int nod)
{
    if (GR[nod]==nod) return GR[nod];
    GR[nod]=grupa(GR[nod]);
    return GR[nod];
}

void unite(int x, int y)
{
    GR[grupa(x)]=grupa(y);
}

int main()
{
    f>>N>>M;
    for (int i=1; i<=N; ++i)
        GR[i]=i;

    while (M--)
    {
        f>>tip>>x>>y;
        if (tip==1) unite(x, y);
            else
            {
                if (grupa(x)==grupa(y)) g<<"DA\n";
                    else g<<"NU\n";
            }
    }
    return 0;
}