Cod sursa(job #2909815)

Utilizator anne_marieMessner Anne anne_marie Data 16 iunie 2022 00:17:14
Problema Paduri de multimi disjuncte Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
using namespace std;
ifstream fin ("disjoint.in");
ofstream fout ("disjoint.out");

int n, m, queryType, x, y;
struct node
{
  int h, t;
} v[100005];
int goToTata(int x){
    int d = x;
    while(d != v[d].t){
        d = v[d].t;
    }
    while(x != d){
        int aux = v[x].t;
        v[x].t = d;
        x = aux;
    }
    return d;
}


// join multimile lui x si y 
void join (int x, int y)
{
    
    x = goToTata(x);
    y = goToTata(y);
    
  if (v[x].h == v[y].h) {
      v[x].t = y;
      v[y].h++;
    }
  else {
      if (v[x].h > v[y].h) {
	  v[y].t = x;
	   }
      else {
	  v[x].t = y;
	   }
    }
}


// verifica daca x si y sunt in aceeasi multime
int verif (int x, int y)
{
    x = goToTata(x);
    y = goToTata(y);
    if (x == y)
        return 1;
    else
        return 0;
}

int
main ()
{
  fin >> n >> m;

  for (int i = 1; i <= n; i++)
    {
      v[i].t = i;
      v[i].h = 0;
    }

  for (int i = 1; i <= m; i++)
    {
      fin >> queryType >> x >> y;
      if (queryType == 1)
	{
	  join (x, y);
	}
      else
	{
	  if (verif (x, y))
	    fout << "DA\n";
	  else
	    fout << "NU\n";
	}
    }
  return 0;
}