Kager min cut図の最小分割アルゴリズム実装

図の定義は一般的なアルゴリズム教材と一致し、無方向図と有方向図に分けられ、一般的に臨接行列と臨接表の表現法があり、2つの具体的なパラメータを含み、Vで図のノード(vertices)個数とEが図のエッジ(edge)の数(Graph(V,E))を指し、具体的な紹介は「アルゴリズム導論」または「アルゴリズム第4版」を参照してください.図の最小分割:
1つのグラフgraph(V,E)の分割:図をノード別に2つの非空セットAとB----cut(A,B)に分割する.
Cut(A,B)のcrossing edge:無方向図で、2つの端点はそれぞれ2つの点セット内にある.方向図があります:辺の尾の結点はAで、頭の結点はBです
総分割数(可能性):最終的に2つの非空点セットがある場合、合計n点があると仮定し、このn点はそれぞれAまたはB内で待つ可能性があり、2つの可能性があるため、合計2^nの分割方式がある.
最小分割:図の分割数が最も少ないcrossing edge.
質問:
入力:平行エッジの存在を可能にする無方向図G=(V,E)
出力:図の最小分割数(crossing edgeの最小分割数)を計算します.
アルゴリズム:確率アルゴリズムで、最小値を複数回計算する

import java.io.IOException;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;

public class KargerMinCut {

    public static void main(String[] args) throws IOException {
        KargerMinCut mc = new KargerMinCut();
        int min = mc.mincut();
        
        
        for (int i = 0; i < 1000; i++){
            mc = new KargerMinCut();
            int ans = mc.mincut();
            if ( ans < min) {
                min = ans;
            }
        }
        
        System.out.println(min);
    }
    
    //       ，      
    List> vergroups = new LinkedList<>();
    
    HashSet> Graph = new HashSet<>();
    
    public int mincut() throws IOException {
        Random r = new Random();
        HashSet vertices = new HashSet<>();
        int vsize = 0;

        Scanner in1 = new Scanner(Paths.get(""));  //     
        
        while (in1.hasNextLine()) {
            vsize++;
            String line = in1.nextLine();
            Scanner readInt = new Scanner(line);
            int v = readInt.nextInt();
            while (readInt.hasNextInt()) {
                Graph.add(new ArrayList() {{ add(v); add(readInt.nextInt());}});
            }
            readInt.close();
        }
        in1.close();
        
        for (int i=1; i<=vsize; i++) {
            vertices.add(i);
        }

        while (true) {
            if ((vergroups.size()==2 && vertices.size()==0) ||
                    ((vergroups.size()==1) && vertices.size()==1)) {
                break;
            }

            ArrayList[] a = new ArrayList[0];
            ArrayList[] g = Graph.toArray(a);
            ArrayList pair = g[r.nextInt(g.length)];

            int v = pair.get(0);
            int u = pair.get(1);
            
            Iterator> i = vergroups.iterator();
            HashSet conV = new HashSet();
            HashSet conU = new HashSet();
            if (!i.hasNext()) {
                vergroups.add(new HashSet(pair));
                vertices.remove(u);
                vertices.remove(v);
            }
            else 
            while (i.hasNext()) {
                HashSet h = i.next();
                
                if (h.contains(v)) {
                    conV = h;
                }
                else if (h.contains(u)) {
                    conU = h;
                }
            }
            
            if (conV.contains(v) && !conU.contains(u)) {
                conV.add(u);                    
                vertices.remove(u);
                removeloop(conV, v, u);
            }
            else if (!conV.contains(v) && conU.contains(u)) {
                conU.add(v);                    
                vertices.remove(v);
                removeloop(conU, u, v);
            }
            else if (!conV.contains(v) && !conU.contains(u) && !vergroups.contains(new HashSet(pair))) {
                vergroups.add(new HashSet(pair));
                vertices.remove(u);
                vertices.remove(v);
            }
            else if (conV.contains(v) && conU.contains(u)) {
                conV.addAll(conU);
                vergroups.remove(conU);
                removeloop(conV, conU, v, u);
            }

            deledge(v, u);
        }
        
        return Graph.size()/2;
    }

    
    public void deledge(int v, int u) {
        List t1 = new ArrayList(2); 
        t1.add(v); t1.add(u);
        List t2 = new ArrayList(2); 
        t2.add(u); t2.add(v);
        Graph.remove(t1);
        Graph.remove(t2);
        
    }
    
    public HashSet preprocess(int v, int u) {
        for (HashSet h : vergroups) {
            if (h.contains(v)) return h;
            else if (h.contains(u)) return h;
        }
        return null;
    }
    
    public void removeloop(HashSet h, int v, int u) {
        for (Integer l : h) {
            if (l != u && l != v) {
                deledge(l, u);
                System.out.println("l:" + l + "  " + "u:" + u);
            }
        }
    }
    
    public void removeloop(HashSet V, HashSet U, int v, int u) {
        for (Integer exu : U) {
            if (exu != u)
            for (Integer j : V) {
                deledge(exu, j);
            }
        }
    }

}