package javaapplication14;

import com.sun.xml.internal.ws.api.pipe.NextAction;
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;

import java.util.regex.Pattern;

/**
 *
 * @author karlo
 */
public class Rcontraction {

    public static void main(String arg[]) {
        ArrayList<ArrayList<Integer>> nodes = new ArrayList();
        ArrayList<obj1> edges = new ArrayList();
        ArrayList<Integer> prueba1 = new ArrayList();
        String hola1;
        int hola2;
        int minimo = 99999;


        try {
            // Open the file that is the first
            // command line parameter
            FileInputStream fstream = new FileInputStream("src/kargerAdj.txt");
            // Get the object of DataInputStream
            DataInputStream in = new DataInputStream(fstream);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine;
            //Read File Line By Line
            while ((strLine = br.readLine()) != null) {
                // Print the content on the console
                hola1 = (strLine);
                Pattern split = Pattern.compile("[,\\s]+");
                String[] result = split.split(hola1);

                prueba1 = new ArrayList();
                for (int i = 1; i < result.length; i++) {
                    prueba1.add(Integer.parseInt(result[i]));
                }
                nodes.add(prueba1);

            }
            //Close the input stream
            in.close();
        } catch (Exception e) {//Catch exception if any
            System.err.println("Error: " + e.getMessage());
        }





        try {
            // Open the file that is the first
            // command line parameter
            FileInputStream fstream = new FileInputStream("src/edges.txt");
            // Get the object of DataInputStream
            DataInputStream in = new DataInputStream(fstream);
            BufferedReader br = new BufferedReader(new InputStreamReader(in));
            String strLine;
            //Read File Line By Line
            while ((strLine = br.readLine()) != null) {
                // Print the content on the console
                hola1 = (strLine);
                Pattern split = Pattern.compile("[,\\s]+");
                String[] result = split.split(hola1);

                obj1 hola = new obj1();
                hola.setNum1(Integer.parseInt(result[0]));
                hola.setNum2(Integer.parseInt(result[1]));
                edges.add(hola);

            }
            //Close the input stream
            in.close();
        } catch (Exception e) {//Catch exception if any
            System.err.println("Error: " + e.getMessage());
        }


        int p = 1;
        ArrayList<ArrayList<Integer>> nodesfinal = new ArrayList();
        ArrayList<ArrayList<Integer>> nodesminimo = new ArrayList();
        while (p < 1000000) {
            nodesfinal = new ArrayList();

            nodesfinal = RandomContraction(nodes, edges);

            if (minimo > nodesfinal.get(0).size()) {
                minimo = nodesfinal.get(0).size();
                nodesminimo = nodesfinal;
            } else if (minimo > nodesfinal.get(1).size()) {
                minimo = nodesfinal.get(1).size();
                nodesminimo = nodesfinal;
            }
            p++;
        }


        System.out.println(minimo);
        System.out.println(nodesminimo);

    }

    private static ArrayList<ArrayList<Integer>> RandomContraction(ArrayList<ArrayList<Integer>> nodes, ArrayList<obj1> edges) { //agregar entrada es un grafo
//         ArrayList<ArrayList<Integer>> nodes = new ArrayList();
//         ArrayList<obj1> edges = new ArrayList();
        try {
                   while (nodes.size() > 2) {
            int numberEdgeToMerge = (int) Math.floor(edges.size() * Math.random());
            obj1 edgeToMerge = new obj1();
            obj1 edgeToMerge2 = new obj1();
            edgeToMerge.setNum1(edges.get(numberEdgeToMerge).getNum1());
            edgeToMerge.setNum2(edges.get(numberEdgeToMerge).getNum2());
            edgeToMerge2.setNum1(edges.get(numberEdgeToMerge).getNum1());
            edgeToMerge2.setNum2(edges.get(numberEdgeToMerge).getNum2());

            //juntar esos


            for (int i = 0; i < nodes.size(); i++) {
                if (nodes.get(i).get(0) == edgeToMerge.getNum1()) {
                    edgeToMerge.setNum1(i + 1);
                } else if (nodes.get(i).get(0) == edgeToMerge.getNum2()) {
                    edgeToMerge.setNum2(i + 1);
                }
            }


            // juntar los nodos vecinos de los 2 nodos del edge seleccionado
            try {
                nodes.get(edgeToMerge.getNum1() - 1).addAll(nodes.get(edgeToMerge.getNum2() - 1).subList(1, nodes.get(edgeToMerge.getNum2() - 1).size()));
            } catch (java.lang.IndexOutOfBoundsException e) {

            }
            for (int i = 0; i < edges.size(); i++) { //para cada nodo
                if (edges.get(i).getNum1() == edgeToMerge2.getNum2()) {
                    edges.get(i).setNum1(edgeToMerge2.getNum1());
                } else if (edges.get(i).getNum2() == edgeToMerge2.getNum2()) {
                    edges.get(i).setNum2(edgeToMerge2.getNum1());
                }
            }

            // quitar repeticiones
            for (int i = 0; i < nodes.size(); i++) { //para cada nodo
                for (int j = 1; j < nodes.get(i).size(); j++) { // para cada vecino del nodo
                    if (nodes.get(i).get(j) == edgeToMerge2.getNum2()) {    //si estaba conectado al segundo nodo combinado
                        nodes.get(i).set(j, edgeToMerge2.getNum1());        //se cambia de nombre para estar conectado al segundo
                    }
                }
            }
            for (int i = 1; i < nodes.get(edgeToMerge.getNum1() - 1).size(); i++) {
                if (nodes.get(edgeToMerge.getNum1() - 1).get(i) == edgeToMerge2.getNum1()) {
                    nodes.get(edgeToMerge.getNum1() - 1).remove(i);
                    i--;
                }
            }
            //borrar ese edge de la lista de edges
            edges.remove(numberEdgeToMerge);

            try {
                nodes.remove(edgeToMerge.getNum2() - 1);
            } catch (java.lang.IndexOutOfBoundsException e) {

            }
            //borrar ese nodo
        }
        return nodes; //que regrese el minimo de cruces
        } catch (Exception e) {
            return nodes;
        }


    }
}