Voltar

UnionFind - Estrutura de dados

0 Curtidas
/* Data Structures: Unionfind with array
   Notes:       The array sets must be initialized to -1.  Negative
                numbers in the array represent the size of the set
associated with that element, while positive numbers
serve as a link back to the root of the set.
*/

#include 
#include 

#define MAXN 1000

int sets[MAXN];

int getRoot(int x){
  if(sets[x] < 0) return x;
  return sets[x] = getRoot(sets[x]);
}

void Union(int a, int b){
  int ra = getRoot(a);
  int rb = getRoot(b);

  if(ra != rb){
    sets[ra] += sets[rb];
    sets[rb] = ra;
  }
}

int main(){
  int a, b, i, n, m;
  
  while(scanf("%d %d", &n, &m) == 2){
    memset(sets, -1, sizeof(sets));
    for(i = 0; i < m; i++){
      scanf("%d %d", &a, &b);
      Union(a,b);
    }
    for(i = 0; i < n; i++){
      printf("%d belongs in the set with [%d]\n", i, getRoot(i));
    }
  }
  return 0;
}
Problemas relacionados
  Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo
Sugestão de livro

Comentários


Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.