POJ 1679クルスカルkruskalアルゴリズムの練習

クルーズカールkruskalアルゴリズム
WN=(V,{E})がn個の頂点を含む連通網であると仮定すると,最小生成ツリーをクルーズカールアルゴリズムに従って構築する過程は以下の通りである.
まず、n個の頂点のみを含み、エッジセットが空のサブマップを構築し、このサブマップの各頂点を各ツリーのルートノードと見なすと、n個のツリーを含む森である.その後、網のエッジセットEから重み値が最も小さいエッジを選択し、そのエッジの2つの頂点が異なるツリーに属している場合、サブマップに追加する.すなわち、この2つの頂点がそれぞれ存在する2つのツリーを1つのツリーに合成する.逆に、エッジの2つの頂点が同じツリーに落ちている場合は、望ましくありません.重みの最小値のエッジを取ってから試してください.サブ図にn−1エッジが含まれるまで順次類推する.
POJ1679:The Unique MST
題意:無方向図を与えて、この図の最小生成木MSTが唯一であるかどうかを判断する.ユニークであれば最小生成ツリーの重み値を出力し、ユニークでなければ「Not Unique!」を出力します. 
分析:まず最小生成木を求め、最小重み値をmstと記す.次に、ツリー上の各エッジを列挙する、削除してから最小生成ツリーを求め、重み値がmstに等しい限り、最小生成ツリーは一意ではない.
サンプル:
Sample Input
2(試験回数)
3 3(頂点とエッジの数)
1 2 1(1辺の2つの頂点と重み値、以下同じ)
2 3 2
3 1 3
4 4
1 2 2
2 3 2
3 4 2
4 1 2
Sample Output
3
Not Unique!
ACコード:

import java.util.Scanner;      
import java.util.Arrays;      
public class Main{      
    private int father[];    //          
    private Edge e[];   //        
    private int n;//          
    private int l;//     
    private int mst;//          
    private boolean uni;//            

    public Main(int n,int l,Edge[] e){      
       this.n=n;      
       this.l=l;      
       this.e=e;      
       father=new int[n+1];  
       mst=0;
       uni=true;    
       make_set();     
          
             
    }         

   private void make_set(){//             ( ），       。 
     for( int x = 1; x <= n; x ++)
        father[x] = x;
   }


   private int find_set(int x){// x    
    if(x != father[x])
        father[x] = find_set(father[x]);//    
    return father[x];
    }

    public int getMst(){
      return this.mst;
    }

    public boolean getUni(){
      return this.uni;
    }

  private void kruskal(){
    int  x, y;
    int mst_e[]=new int[n];//       krushal   MST  
    int edge_num=0;//   krushal    ;
    int k = 0;
      //       kruskal MST。
    make_set();    
    Arrays.sort(e);//       （    ）
     for(int i = 0; i < l; i ++){
        x = find_set(e[i].a);
        y = find_set(e[i].b);
        if(x != y){
            father[y] = x;//     
            mst += e[i].weight;
            mst_e[k ++] = i;   //     MST  。
        }
    }
    edge_num = k;//    MST     
   
   
    for(int r = 0; r < edge_num; r ++){//        ,             ,
         make_set();     //    kruskal         。
         int sec_mst=0;//                   
         int num = 0;
        for(int i = 0; i < l; i ++){
            if(i == mst_e[r]) continue;   //      。
            x = find_set(e[i].a);
            y = find_set(e[i].b);
            if(x != y){
                father[y] = x;
                sec_mst += e[i].weight;
                num ++;
            }
        }
        if(num != edge_num) continue;   //              。
        if(sec_mst == mst){
         //System.out.println(mst);
  //              ，          mst  ，   MST   。
            uni = false;
            return;
        }
    } 
}

 

 public static void main(String args[]){
    Scanner in=new Scanner(System.in);
    int t=in.nextInt();
    
    while(t -->0){
        int n=in.nextInt();//   
        int m=in.nextInt();//  
        Edge[] e=new Edge[m];   
      for(int i = 0; i <m; i++){   
          e[i]=new Edge(in.nextInt(),in.nextInt(),in.nextInt());   
             
      }   
      Main ma=new Main(n,m,e);   
     
      ma.kruskal();
        if(!ma.getUni()) System.out.printf("Not Unique!
");
        else System.out.printf("%d
", ma.getMst());
    }
  }
  
}


class Edge implements Comparable       
     
{        
     int a;  //      ，   0        
     int b;  //             
     int weight;  //        
     
     Edge(int a,int b,int weight){      
      this.a=a;      
      this.b=b;      
      this.weight=weight;      
    }      
     
    @Override         
    public int compareTo(Object o){       
        Edge m = (Edge)o;       
        int result=(int)(this.weight - m.weight);       
        if(result>0) return 1;      
        else if(result==0) return 0;      
        else return -1;      
    }       
     
}