Disjoint set

From Progteam

Revision as of 19:11, 22 October 2007 by Hjfreyer (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
import java.util.*;

class DisjointSet<T> {
    HashMap<T,T> parent;
    Random rand;

    public DisjointSet(){
	rand=new Random();
	parent=new HashMap<T,T>();
    }

    public void union(T a, T b){
	if(a.equals(b))
	    return;
	if(parent.get(a).equals(a) && parent.get(b).equals(b)){
	    if(rand.nextBoolean())
		parent.put(b,a);
	    else
		parent.put(a,b);
	    return;
	}
	union(find(a),find(b));	
    }
    
    public boolean equal(T a, T b){
	return find(a).equals(find(b));
    }

    public T find(T x){
	if(parent.get(x).equals(x))
	    return x;
	T p=find(parent.get(x));
	parent.put(x,p);
	
	return p;
    }

    public void add(T t){
	parent.put(t,t);
    }
}
Personal tools