package prim;

import java.util.*;

public class Prim {

    PriorityQueue<Solmu> keko;
    ArrayList<Solmu>[] vieruslista;
    int[] etaisyys;
    Solmu[] vanhempi;
    int[][] painot;
    boolean[] onkoPuussa;
    Solmu[] verkko;
    int n;
    int maara;

    public Prim(int n) {
        this.keko = new PriorityQueue<>();
        this.vieruslista = new ArrayList[n+1];
        this.etaisyys = new int[n+1];
        this.vanhempi = new Solmu[n+1];
        this.painot = new int[n+1][n+1];
        this.onkoPuussa = new boolean[n+1];
        this.verkko = new Solmu[n+1];
        this.n = n;
        this.maara = 0;

        for (int i = 1; i <= n; i++) {
            vieruslista[i] = new ArrayList();
        }

        onkoPuussa[1] = true;

        etaisyys[1] = 0;

        for (int i = 2; i <= n; i++) {
            etaisyys[i] = Integer.MAX_VALUE;
        }

    }

    public class Solmu implements Comparable {

        public int numero, etaisyys;

        public Solmu(int solmu) {
            this.numero = solmu;
            this.etaisyys = Integer.MAX_VALUE;
        }

        @Override
        public int compareTo(Object o) {
            Solmu toinen = (Solmu) o;
            return this.etaisyys - toinen.etaisyys;
        }
    }

    public void lisaaTie(int a, int b, int x) {

        if (painot[a][b] > 0 && painot[a][b] < x) {
            return;
        }

        Solmu solmuA = new Solmu(a);
        Solmu solmuB = new Solmu(b);

        painot[a][b] = x;
        painot[b][a] = x;

        vieruslista[a].add(solmuB);
        vieruslista[b].add(solmuA);
    }

    public int laske() {

        Solmu eka = new Solmu(1);
        eka.etaisyys = 0;
        keko.add(eka);
        verkko[1] = eka;

        for (int i = 2; i <= n; i++) {
            Solmu uusi = new Solmu(i);
            verkko[i] = uusi;
            keko.add(uusi);
        }

        int paino = 0;
        Solmu solmu;

        while (maara <= n) {

            if (keko.isEmpty()) {
                break;
            }

            solmu = keko.poll();

            if (vanhempi[solmu.numero] != null) {
                int u = solmu.numero;
                int uv = vanhempi[solmu.numero].numero;

                if (!onkoPuussa[solmu.numero]) {
                    maara++;
                }

                onkoPuussa[solmu.numero] = true;
            }

            for (int i = 0; i < vieruslista[solmu.numero].size(); i++) {

                Solmu v = vieruslista[solmu.numero].get(i);

                if (!onkoPuussa[v.numero] && painot[solmu.numero][v.numero] < etaisyys[v.numero]) {
                    vanhempi[v.numero] = solmu;
                    etaisyys[v.numero] = painot[solmu.numero][v.numero];
                    v.etaisyys = painot[solmu.numero][v.numero];
                    keko.add(v);
                }
            }
        }

        for (int i = 2; i <= n; i++) {
            paino = paino + painot[vanhempi[i].numero][i];
        }

        return paino;
    }

    public static void main(String[] args) {

        HashSet<Integer> solmut = new HashSet<>();

        int n = 5000;
        int m = 100000;

        Prim k = new Prim(n);

        Random r = new Random(1337);
        for (int i = 1; i <= m; i++) {
            int a = r.nextInt(n) + 1;
            int b = r.nextInt(n) + 1;
            int x = r.nextInt(1000) + 1;
            k.lisaaTie(a, b, x);

            solmut.add(a);
            solmut.add(b);
        }

        long alku = System.nanoTime();

        System.out.println(k.laske());

        long loppu = System.nanoTime();

        System.out.println("Aikaa kului " + ((loppu-alku) / 1e9) + " s");
    }

}