Cod sursa(job #1727388)

Utilizator bghimisFMI Ghimis Bogdan bghimis Data 10 iulie 2016 17:51:23
Problema Paduri de multimi disjuncte Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 0.7 kb
#include <stdio.h>

typedef struct nod {
  int value;
  struct nod* parent;
} node;

node v[100005];

void _union (int a, int b) {
  v[a].parent = &v[b];
}

int _find (int a) {
  node crt = v[a];
  while (crt.parent != NULL)
    crt = *crt.parent;

  return crt.value;
}

int main (){
  freopen ("disjoint.in", "r", stdin);
  freopen ("disjoint.out", "w", stdout);
  
  int n, m;
  scanf ("%d%d", &n, &m);

  int i;
  for (i = 1; i <= n; ++i) {
    v[i].value = i;
    v[i].parent = NULL;
  }

  for (i = 1; i <= m; ++i) {
    int t; scanf ("%d", &t);
    int a, b; scanf ("%d%d", &a, &b);

    if (t == 1)
      _union (a, b);
    else
      printf ("%s\n", _find(a) == _find(b) ? "DA" : "NU");
  }
  
  return 0;
}