Cod sursa(job #2457635)

Utilizator matei123Biciusca Matei matei123 Data 18 septembrie 2019 12:33:12
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <fstream>
using namespace std;
ifstream fin("disjoint.in"); ofstream fout("disjoint.out");
const int N = 1e6 + 5;
int t[N];
void Union (int x, int y) ///unifica 2 arbori cu radacini x si y
{   t[y] = x;  }
int Find (int x) /// afla radacina compenentei conexe a lui x
{   int root, y;
    root = x;
    while (t[root] != 0) root = t[root];
    /// comprimare drum
    while (x != root)
    {   y = t[x];
        t[x] = root;
        x = y;
    }
    return root;
}
void Solve ()
{   int n, m;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {   int op, x, y;
        fin >> op >> x >> y;
        x = Find(x);
        y = Find(y);
        if (op == 1)
        {   if (x != y) Union(x, y); }
        else
        {   if (x == y) fout << "DA\n";
            else fout << "NU\n";
        }
    }
}
int main()
{   Solve();
    return 0;
}