import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Random;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

public class Graf {
    private Integer liczbaWierzcholkow;
    private Integer[][] macierz;

    public Graf(final int liczbaWierzcholkow) {
        this.liczbaWierzcholkow = liczbaWierzcholkow;
        this.macierz = initMacierzy(liczbaWierzcholkow);
    }

    private Integer[][] initMacierzy(int liczbaWierzcholkow) {
        Integer[][] retVal = new Integer[liczbaWierzcholkow][liczbaWierzcholkow];

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                retVal[i][j] = 0;
            }
        }

        return retVal;
    }

    public void dodajKrawedz(Integer od, Integer doo) {
        if (od != doo) {
            macierz[od][doo] = 1;
            macierz[doo][od] = 1;
        }
    }

    public void usunKrawedz(Integer od, Integer doo) {
        if (od != doo) {
            this.macierz[od][doo] = 0;
            this.macierz[doo][od] = 0;
        }
    }

    public void dodajWierzcholek() {
        Integer[][] tmpMacierz = initMacierzy(liczbaWierzcholkow + 1);

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                tmpMacierz[i][j] = macierz[i][j];
            }
        }

        liczbaWierzcholkow++;
        this.macierz = tmpMacierz;
    }

    public void usunWierzcholek(Integer indexWierzcholka) {
        ArrayList<ArrayList<Integer>> tmp = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            if (i != indexWierzcholka) {
                tmp.add(new ArrayList<Integer>());
                for (int j = 0; j < liczbaWierzcholkow - 1; j++) {
                    if (i != 0)
                        tmp.get(i - 1).add(macierz[i - 1][j]);
                    else
                        tmp.get(i).add(macierz[i][j]);
                }
            }
        }

        liczbaWierzcholkow--;

        Integer[][] retVal = new Integer[liczbaWierzcholkow][liczbaWierzcholkow];

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                retVal[i][j] = tmp.get(i).get(j);
            }
        }

        macierz = retVal;
    }

    public Integer getSopienWierzcholka(int indexWierzcholka) {
        Integer suma = 0;

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            if (macierz[indexWierzcholka][i] != 0) {
                suma++;
            }
        }

        return suma;
    }

    public Integer getMinStopien() {
        Integer minimum = Integer.MAX_VALUE;

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            Integer stopienWierzcholka = this.getSopienWierzcholka(i);
            if (stopienWierzcholka < minimum) {
                minimum = stopienWierzcholka;
            }
        }

        return minimum;
    }

    public Integer getMaxStopien() {
        Integer maximum = Integer.MIN_VALUE;

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            Integer stopienWierzcholka = this.getSopienWierzcholka(i);
            if (stopienWierzcholka > maximum) {
                maximum = stopienWierzcholka;
            }
        }

        return maximum;
    }

    public Integer zliczWierzcholkiStopniaParzystego() {
        Integer suma = 0;

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            if (this.getSopienWierzcholka(i) % 2 == 0) {
                suma++;
            }
        }

        return suma;
    }

    public Integer zliczWierzcholkiStopniaNieparzystego() {
        Integer suma = 0;

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            if (this.getSopienWierzcholka(i) % 2 == 1) {
                suma++;
            }
        }

        return suma;
    }

    public Integer[] getCiagStopni() {
        ArrayList<Integer> stopnie = new ArrayList<Integer>();

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            stopnie.add(this.getSopienWierzcholka(i));
        }

        Collections.reverse(stopnie);

        return stopnie.toArray(new Integer[stopnie.size()]);
    }

    @Override
    public String toString() {
        StringBuilder s = new StringBuilder();

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                s.append(macierz[i][j]).append(" ");
            }
            s.append("\n");
        }

        return s.toString();
    }

    public boolean getC3Naiwnie() {
        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                if (i != j && macierz[i][j] != 0) {
                    for (int k = 0; k < liczbaWierzcholkow; k++) {
                        if (k != i && j != k && macierz[j][k] != 0) {
                            if (macierz[k][i] != 0) {
                                return true;
                            }
                        }
                    }
                }
            }
        }

        return false;
    }

    public boolean getC3() {
        Integer[][] spotegowanaMacierz = potegaMacierzy();

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                if (i != j && macierz[i][j] == 1 && spotegowanaMacierz[i][j] >= 1) {
                    return true;
                }
            }
        }

        return false;
    }

    public Integer[][] potegaMacierzy() {
        Integer[][] retVal = new Integer[liczbaWierzcholkow][liczbaWierzcholkow];

        for (int i = 0; i < liczbaWierzcholkow; i++) {
            for (int j = 0; j < liczbaWierzcholkow; j++) {
                retVal[i][j] = 0;
                for (int k = 0; k < liczbaWierzcholkow; k++) {
                    retVal[i][j] += macierz[i][k] * macierz[k][j];
                }
            }
        }

        return retVal;
    }

    /*
     *
     * ZADANIE 1
     */

    public ArrayList<Integer> getCykl() {

        if (liczbaWierzcholkow < 3 && getMinStopien() < 2) {
            System.out.println("Graf nie jest poprawny");
            return null;
        }

        for (int pierwszy = 0; pierwszy < liczbaWierzcholkow; pierwszy++) {
            ArrayList<Integer> sciezka = new ArrayList<Integer>();

            Integer nieodwiedzony = pierwszy;
            while (nieodwiedzony != null) {
                sciezka.add(nieodwiedzony);

                nieodwiedzony = getNieodwiedzonyWierzcholek(sciezka);
            }

            ArrayList<Integer> sciezkaKopia = (ArrayList<Integer>) sciezka.clone();

            while (sciezkaKopia.size() > 2) {
                if (istniejeKrawedz(sciezkaKopia.get(0), sciezkaKopia.get(sciezkaKopia.size() - 1))) {
                    return sciezkaKopia;
                }

                sciezkaKopia.remove(sciezkaKopia.size() - 1);
            }

            while (sciezka.size() > 2) {
                if (istniejeKrawedz(sciezka.get(0), sciezka.get(sciezka.size() - 1))) {
                    return sciezka;
                }

                sciezka.remove(0);
            }
        }

        return null;
    }

    private Integer getNieodwiedzonyWierzcholek(ArrayList<Integer> sciezka) {
        Integer ostatni = sciezka.get(sciezka.size() - 1);

        for (int wierzcholek = 1; wierzcholek < liczbaWierzcholkow; wierzcholek++) {
            if (ostatni != wierzcholek && istniejeKrawedz(ostatni, wierzcholek) && !sciezka.contains(wierzcholek)) {
                return wierzcholek;
            }
        }

        return null;
    }

    private boolean istniejeKrawedz(Integer od, Integer doo) {
        return macierz[od][doo] != 0;
    }

    /*
     *
     * ZADANIE 3
     */

    // glebokosc - wierzcholek
    private HashMap<Integer, ArrayList<Integer>> glebokosciWierzcholkow = new HashMap<Integer, ArrayList<Integer>>();
    // wierzcholek - rodzic
    private HashMap<Integer, Integer> rodziceWierzcholkow = new HashMap<Integer, Integer>();
    // wierzcholek - [aktualny, czyDziecko] niestety tuple w javie sa slabe,
    // uzywam tablicy 2 elementowej
    private HashMap<Integer, Boolean[]> wierzcholkiDominujace = new HashMap<Integer, Boolean[]>();

    public ArrayList<Integer> getMinDomZbior() {
        if (liczbaWierzcholkow < 1) {
            System.out.println("Nie prawidlowe drzewo");
            return null;
        }

        Integer korzen = wylosujKorzen();

        initGrafUkorzeniony(korzen, 0, -1);

        return znajdzZbiorDominujacy();
    }

    private Integer wylosujKorzen() {
        Random r = new Random();
        return r.nextInt(liczbaWierzcholkow);
    }

    private void initGrafUkorzeniony(Integer wierzcholek, Integer glebokosc, Integer rodzic) {
        if (!glebokosciWierzcholkow.containsKey(glebokosc)) {
            glebokosciWierzcholkow.put(glebokosc, new ArrayList<Integer>());
        }

        glebokosciWierzcholkow.get(glebokosc).add(wierzcholek);
        rodziceWierzcholkow.put(wierzcholek, rodzic);
        wierzcholkiDominujace.put(wierzcholek, new Boolean[] { false, false });

        for (Integer wtmp = 0; wtmp < liczbaWierzcholkow; wtmp++) {
            if (wierzcholek != wtmp && wtmp != rodzic && istniejeKrawedz(wierzcholek, wtmp)) {
                initGrafUkorzeniony(wtmp, glebokosc + 1, wierzcholek);
            }
        }
    }

    private ArrayList<Integer> znajdzZbiorDominujacy() {
        for (int i = glebokosciWierzcholkow.size() - 1; i >= 0; i--) {
            for (int j = 0; j < glebokosciWierzcholkow.get(i).size(); j++) {
                Integer wierzcholek = glebokosciWierzcholkow.get(i).get(j);
                Integer rodzic = rodziceWierzcholkow.get(wierzcholek);

                if (!wierzcholkiDominujace.get(wierzcholek)[0] && !wierzcholkiDominujace.get(wierzcholek)[1]) {
                    if (rodzic != -1) {
                        Integer praDziad = rodziceWierzcholkow.get(rodzic);

                        // przepisanie pary z wartoscia true dla "aktualny"
                        wierzcholkiDominujace.get(rodzic)[0] = true;

                        if (praDziad != -1) {
                            wierzcholkiDominujace.get(praDziad)[1] = true;
                        }
                    } else {
                        wierzcholkiDominujace.get(wierzcholek)[0] = true;
                    }
                }
            }
        }

        ArrayList<Integer> zbiorDominujacy = new ArrayList<Integer>();
        wierzcholkiDominujace.forEach((wierzcholek, dom) -> {
            if (dom[0]) {
                zbiorDominujacy.add(wierzcholek);
            }
        });

        return zbiorDominujacy;
    }

    public Stack<Integer> znajdzEulera() {
        Stack<Integer> stos = new Stack<Integer>();
        Stack<Integer> euler = new Stack<Integer>();
        Random r = new Random();
        Integer u = r.nextInt(liczbaWierzcholkow);
        Integer v = null;
        euler.push(u);

        do {
            v = getNastepnyWierzcholek(u);
            if (v != null) {
                stos.push(u);
                usunKrawedz(u, v);
                u = v;
            } else {
                euler.push(stos.pop());
            }
        } while (stos.toArray().length > 0);

        return euler;
    };

    public Integer getNastepnyWierzcholek(Integer n) {
        for (int j = 0; j < liczbaWierzcholkow; j++) {
            if (macierz[n][j] != 0)
                return j;
        }

        return null;
    }

    public Integer getNastepnyWierzcholekNieBedacyWStosieIBedacyWiekszyOdPoprzedniegoZdjetego(Integer n, Stack<Integer> stos,
            Integer poprzedni) {
        for (int j = 0; j < liczbaWierzcholkow; j++) {
            if (!stos.contains(j) && j > poprzedni && macierz[n][j] != 0)
                return j;
        }

        return null;
    }

    public Stack<Integer> znajdzHamiltona() {
        Stack<Integer> stos = new Stack<Integer>();
        Random r = new Random();
        Integer v = r.nextInt(liczbaWierzcholkow);
        Integer poprzedniZdjety = -1;
        Integer u = v;
        Integer w = -1;
        stos.push(v);

        while (stos.size() < liczbaWierzcholkow) {
            u = stos.lastElement();

            if ((w = getNastepnyWierzcholekNieBedacyWStosieIBedacyWiekszyOdPoprzedniegoZdjetego(u, stos, poprzedniZdjety)) != null) {
                stos.push(w);
            } else {
                poprzedniZdjety = stos.pop();
            }
        }

        return stos;
    }
}