fastunionfind.java

来自「《算法设计与分析》王晓东编著」· Java 代码 · 共 37 行

public class FastUnionFind {
   private Tree[] unionTree;
   private Tree[] root; 
   private int n;
   
   public FastUnionFind(int n)
   {
	   unionTree=new Tree[n+1];	 
	   root=new Tree[n+1];
	   for (int i=1;i<=n;i++)
	   {
		   unionTree[i]=new Tree();
		   unionTree[i].node=i;
		   root[i]=unionTree[i];
	   }
	   this.n=n;
   }
   
   public int find(int nodeindex)
   {	   
	   if (nodeindex>n || nodeindex<1) return -1;
	   Tree temp=unionTree[nodeindex];
	   while (temp.upper!=null) temp=temp.upper;
	   return temp.node;
   } 
   
   public void union(int a,int b)
   {
	   Tree newtree=new Tree();	   
	   newtree.node=root[a].node;
	   root[a].upper=newtree;
	   root[a]=newtree;
	   root[b].upper=newtree;
	   root[b]=null;	   
   }
}