Cod sursa(job #3184393)

Utilizator n6v26rDedu Razvan Matei n6v26r Data 15 decembrie 2023 19:07:48
Problema Paduri de multimi disjuncte Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <stdio.h>

#define MAXN 100001

int sef[MAXN];
int sz[MAXN];

int find(int n){
  if(sef[n]==n)
    return n;
  else return sef[n] = find(sef[n]);
}

void unite(int a, int b){
  int u = find(a);
  int v = find(b);
  if(u==v) return;
  if(sz[u]<sz[v]){
    sef[u] = v;
    sz[v] += sz[u];
  }
  else{
    sef[v] = u;
    sz[u] += sz[v];
  }
}

int main(){
  for(int i=0; i<MAXN; i++) sef[i] = i, sz[i] = 1;
  int n, m;
  FILE *fin, *fout;
  fin = fopen("disjoint.in", "r");
  fout = fopen("disjoint.out", "w");
  fscanf(fin, "%d%d", &n, &m);
  for(int i=0; i<m; i++){
    int op, a, b;
    fscanf(fin, "%d%d%d", &op, &a, &b);
    if(op==1)
      unite(a, b);
    if(op==2){
      if(find(a)==find(b)) fprintf(fout, "DA\n");
      else fprintf(fout, "NU\n");
    }
  }
  fclose(fin);

  fclose(fout);
}