A10

import java.util.*;

import sk.upjs.paz.graph.*;

public class KruskalovAlgoritmus {

        public static void main(String[] args) {
                Graph g = Graph.createFromFile("graf.txt");

                List<Edge> hrany = new ArrayList<>(g.getEdges());
                Graph.sortEdgesByWeight(hrany);

                List<Edge> kostra = new LinkedList<>();
                Map<Vertex, Integer> idKomponentov = new HashMap<>();

                int idx = 0;
                for (Vertex v : g.getVertices()) {
                        idKomponentov.put(v, idx);
                        idx++;
                }

                for (Edge e : hrany)
                        if (!idKomponentov.get(e.getSource()).equals(
                                        idKomponentov.get(e.getTarget()))) {
                                kostra.add(e);
                                int nove = idKomponentov.get(e.getSource());
                                int stare = idKomponentov.get(e.getTarget());
                                for (Vertex v : g.getVertices())
                                        if (idKomponentov.get(v) == stare)
                                                idKomponentov.put(v, nove);
                        }

                System.out.println("Kostra grafu obsahuje hrany: " + kostra + ".");
        }
}