fac10_4_4.java

java 算法设计与分析的好资料.由王晓东先生主编.

//本程序取自王晓东编著“算法分析与设计”第 373 页，例10_4_4
//并查集
   class Node
      {
       int parent;
       boolean  root;
          Node()
         {
           parent=1;
           root=true;
         }
      }
  class UnionFind
   {  
      Node []node;
      UnionFind(int n)
      {
       node=new Node[n+1];
       for(int e=0;e<=n;e++)node[e]=new Node();
      }
    public int find(int e)
     {
      while(! node[e].root) e=node[e].parent;
      return e;
     }
    public void union(int A,int B)
     {
      node[A].parent+=node[B].parent;
      node[B].root=false; 
      node[B].parent=A;
     } 
   }
 public class Fac10_4_4 {   
      public static void main(String args[])
  {
    UnionFind  X=new UnionFind(8);
    UnionFind  y=new UnionFind(4);
    
    System.out.println("the 并查集");
    X.union(8,4);
    System.out.println(X.find(5)+"**********"); 
  }
}