Cod sursa(job #2310303)

Utilizator justsomedudePalade Thomas-Emanuel justsomedude Data 31 decembrie 2018 03:20:27
Problema Paduri de multimi disjuncte Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include<iostream>
#include<fstream>
using namespace std;

ifstream fin ("disjoint.in");
ofstream fout ("disjoint.out");

int c[100002], t[100002];
int N, M;

int Find(int x)
{
   int y, z;
   y = x;
   while (t[x] != 0)
	x = t[x];

   while (t[y] != 0)
   {
	z = t[y];
	t[y] = x;
	y = z;
   }
   return x;
}

void Union(int x, int y)
{
    if (c[x] > c[y])
    {
	c[x] += c[y];
	t[y] = x;
    }
    else
    {
	c[y] += c[x];
	t[x] = y;
    }
}

void Init()
{
   for (int i = 1; i <= N; i++)
   {
	c[i] = 1;
	t[i] = 0;
   }
}

void Solve()
{
   int x, y, type;

   fin >> N >> M;
   for (int i = 1; i <= M; i++)
   {
       fin >> type >> x >> y;
       if (type == 1) Union(x,y);
       else if (Find(x) == Find(y))
		fout << "DA\n";
       else	fout << "NU\n";
   }
}

int main ()
{
   Init();
   Solve();
   return 0;
}