C8

import java.util.*;
import sk.upjs.paz.*;

public class Grafy {

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Integer> bfs(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Integer> navstiveny = new HashMap<Vertex, Integer>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, -1);

                // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial
                // neskusali navstivit
                Queue<Vertex> rad = new LinkedList<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, 0);
                rad.offer(start);

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        // Vyberieme prvy vrchol v rade
                        Vertex v = rad.poll();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich do radu
                        for (Vertex sused : v.getOutNeighbours())
                                if (navstiveny.get(sused) == -1) {
                                        navstiveny.put(sused, navstiveny.get(v) + 1);
                                        rad.offer(sused);
                                }
                }

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholi boli
         *            navstivene
         */
        public static void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused))
                                dfs(sused, navstiveny);
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsRekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);
                return navstiveny;
        }

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsNerekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Vytvorime zasobnik na vrcholy, ktore treba navstivit
                Stack<Vertex> zasobnik = new Stack<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                zasobnik.push(start);

                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol z vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich na vrch zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        zasobnik.push(sused);
                                }
                }

                return navstiveny;
        }

        public static List<Vertex> cestaZ(Map<Vertex, Integer> vzdialenosti,
                        Vertex kam) {
                if (vzdialenosti.get(kam) == -1)
                        return null;

                List<Vertex> vysledok = new ArrayList<Vertex>();
                Vertex aktualny = kam;
                while (vzdialenosti.get(aktualny) > 0) {
                        vysledok.add(aktualny);
                        Vertex najblizsi = aktualny;
                        for (Vertex sused : aktualny.getInNeighbours())
                                if (vzdialenosti.get(sused) < vzdialenosti.get(najblizsi)) {
                                        najblizsi = sused;
                                }

                        aktualny = najblizsi;
                }
                vysledok.add(aktualny);
                Collections.reverse(vysledok);
                return vysledok;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.loadFromFile("graf.txt");

                System.out.println(fb);

                // Spustime rekurzivne dfs
                // Map<Vertex, Integer> vzdialenosti = bfs(fb, fb.getVertex("5"));
                // System.out.println(cestaZ(vzdialenosti, fb.getVertex("2")));
                // Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();
                // navstiveny.put(fb.getVertex("5"), true);
                // navstiveny = dfsRekurzivne(fb, fb.getVertex("5"));
                najdiKomponenty(fb);
                // for (Map.Entry<Vertex, Boolean> entry : navstiveny.entrySet()) {
                // System.out.println("Key : " + entry.getKey() + " Value : "
                // + entry.getValue());
                // }
        }

        public static Map<Vertex, Integer> najdiKomponenty(Graph g) {
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                for (Vertex v : g.getVertices()) {
                        if (!navstiveny.get(v)) {
                                System.out.println("z vrcholu: "+v);
                                navstiveny.put(v, true);
                                navstiveny = dfsRekurzivne(g, v);
                                for (Map.Entry<Vertex, Boolean> entry : navstiveny.entrySet()) {
                                        System.out.println("Key : " + entry.getKey() + " Value : "
                                                        + entry.getValue());
                                }
                                System.out.println("--------------");
                        }
                }

                return null;
        }
}

import java.util.*;

import sk.upjs.paz.*;

public class Grafy {

        /**
         * Realizuje prehladavanie do sirky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> bfs(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Vytvorime rad pre navstivene vrcholy, ktorych susedov sme zatial
                // neskusali navstivit
                Queue<Vertex> rad = new LinkedList<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                rad.offer(start);

                // Kym rad nie je prazdny
                while (!rad.isEmpty()) {
                        // Vyberieme prvy vrchol v rade
                        Vertex v = rad.poll();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich do radu
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        rad.offer(sused);
                                }
                }

                return navstiveny;
        }

        /**
         * Realizuje rekurzivne prehladavanie do hlbky
         *
         * @param v
         *            vrchol, ktory ideme navstivit
         * @param navstiveny
         *            mapa, v ktorej mame informaciu o tom, ktore vrcholi boli
         *            navstivene
         */
        public static void dfs(Vertex v, Map<Vertex, Boolean> navstiveny) {
                navstiveny.put(v, true);

                // Navstivime vsetkych nenavstivenych susedov
                for (Vertex sused : v.getOutNeighbours())
                        if (!navstiveny.get(sused))
                                dfs(sused, navstiveny);
        }

        public static int pocetKomponentov(Graph g) {
                int pocitadlo = 1;
                Map<Vertex, Boolean> navstiveny = dfsRekurzivne(g, g.getVertex("1"));
                for (Vertex m : g.getVertices()) {
                        if (!navstiveny.get(m)) {
                                Map<Vertex, Boolean> novyNavst=dfsRekurzivne(g, m);
                                for (Map.Entry<Vertex, Boolean> entry : novyNavst.entrySet()) {
                                        if(entry.getValue()){navstiveny.put(entry.getKey(),entry.getValue());}
                                }
                                System.out.println();
                                pocitadlo++;
                        }

                }
                return pocitadlo;
        }

        public static Map<Vertex, Integer> kamPatri(Graph g) {
                Map<Vertex, Integer> komponent = new HashMap<Vertex, Integer>();
                int pocitadlo = 1;
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                for (Vertex m : g.getVertices()) {
                        if (!navstiveny.get(m)) {
                                Map<Vertex, Boolean> novyNavst=dfsRekurzivne(g, m);
                                for (Map.Entry<Vertex, Boolean> entry : novyNavst.entrySet()) {
                                        if(entry.getValue()){
                                                navstiveny.put(entry.getKey(),entry.getValue());
                                                komponent.put(entry.getKey(), pocitadlo);
                                                }
                                }
                                System.out.println();
                                pocitadlo++;
                        }

                }
                return komponent;
        }

        /**
         * Realizuje (spusti) rekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsRekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Spustime vyhladavanie z aktualneho vrchola
                dfs(start, navstiveny);
                System.out.println(navstiveny.toString());
                return navstiveny;
        }

        public static boolean jeSuvisly(Map<Vertex, Boolean> navstiveny) {

                for (Map.Entry<Vertex, Boolean> entry : navstiveny.entrySet()) {

                        if (entry.getValue() == false) {
                                return false;
                        }
                }
                return true;
        }

        /**
         * Realizuje nerekurzivne prehladavanie do hlbky
         *
         * @param g
         *            graf, v ktorom sa realizuje prehladavanie
         * @param start
         *            startovaci vrchol, v ktorom startujeme vyhladavanie
         *
         * @return mapa, ktora urcuje, ci sa vrchol navstivil podla prehladavania
         */
        public static Map<Vertex, Boolean> dfsNerekurzivne(Graph g, Vertex start) {
                // Vytvorime mapu
                Map<Vertex, Boolean> navstiveny = new HashMap<Vertex, Boolean>();

                // Oznacime vsetky vrcholy ako nenavstivene
                for (Vertex v : g.getVertices())
                        navstiveny.put(v, false);

                // Vytvorime zasobnik na vrcholy, ktore treba navstivit
                Stack<Vertex> zasobnik = new Stack<Vertex>();

                // Na zaciatku je navstiveny iba startovaci vrchol
                navstiveny.put(start, true);
                zasobnik.push(start);

                while (!zasobnik.isEmpty()) {
                        // Vyberieme vrchol z vrchu zasobnika
                        Vertex v = zasobnik.pop();

                        // Postupne vsetkych nenavstivenych susedov vrcholu v oznacime ako
                        // navstivenych a pridame ich na vrch zasobnika
                        for (Vertex sused : v.getOutNeighbours())
                                if (!navstiveny.get(sused)) {
                                        navstiveny.put(sused, true);
                                        zasobnik.push(sused);
                                }
                }

                return navstiveny;
        }

        /**
         * @param args
         */
        public static void main(String[] args) {
                // Vytvorime graf
                Graph fb = new Graph();
                // Nacitame zoznam hran zo suboru
                fb.loadFromFile("grax.txt");

                // Spustime rekurzivne dfs
                // bfs(fb, fb.getVertex("1"));
                System.out.println(pocetKomponentov(fb));
                System.out.println(jeSuvisly(dfsRekurzivne(fb, fb.getVertex("1"))));
                System.out.println(kamPatri(fb));
        }
}