Union Find

Disjoint-Sets - Union Find 

 

http://www.algorithmist.com/index.php/Union_Find

http://en.wikipedia.org/wiki/Disjoint-set_data_structure
 

Tiene 2 operaciones :

  • Find(A) : Determina a cual conjunto pertenece el elemento A.
    Esta operación puede ser usada para determinar si 2 elementos están o no en el mismo conjunto.
  • Union(A,B) : Une todo el conjunto al que pertenece A con todo el conjunto al que pertenece B, dando como resultado la  union de los elementos de A y de B                          

Codigo:

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <queue>
#include <stack>
#define MAXN 1000
using namespace std;
int padre[MAXN];
void Ini(int m){
  for(int i=0;i<MAXN;i++)padre[i]=i;
}

int Find(int x){
    if( x == padre[x])return x;                
    else return Find(padre[x]);
}

int Union(int x, int y){
padre[Find(x)]=padre[FInd(y)];
}

int main(){
    int tam , k , A , B;
    scanf("%d %d",&V,&k);
    Ini(tam);                    

    while(k--){
        scanf("%d %d",&A,&B);
        Union( A,B )
    }
    return 0;
}

Un ejemplo de como usar Union Find es del problema del UVA 10685 - Nature

En ideone

http://ideone.com/api/embed.js/link/s9Ro7U
Tags: 

Comentarios

Yes! Finally someone writes about Judi Poker, netkasb.com, Online Terpercaya.