Programovanie (2) v Jave
1-INF-166, LS 2017/18

Úvod · Pravidlá · Prednášky · Netbeans · Testovač · Test a skúška
· Vyučujúcich môžete kontaktovať pomocou e-mailovej adresy E-prg.png (bude odpovedať ten z nás, kto má príslušnú otázku na starosti alebo kto má práve čas).
· DÚ10 je zverejnená, odovzdávajte do stredy 16.5. 22:00.
· Bonusový projekt odovzdávajte do pondelka 21.5. 22:00 na testovači. Predvádzanie projektov bude po prvom termíne skúšky v stredu 23.5. (t.j. začneme medzi 11:45 a 12:00 v H6). Ak vtedy nemôžete prísť, kontaktujte vyučujúce, dohodneme iný termín.
· Opravný/náhradný test bude v pondelok 28.5. o 10:00 v F1-108. V prípade záujmu sa prihláste v AISe.
· Na termíny skúšok sa zapisujte v AIS. Termíny: streda 23.5. (riadny), štvrtok 7.6. (riadny alebo 1. opravný), streda 20.6. (1. alebo 2. opravný) plus v prípade potreby ešte jeden termín v poslednom týždni skúškového. Prípadné konflikty nám dajte vedieť čím skôr. Ďalšie informácie na stránke Test a skúška.


Prednáška 35

Z Programovanie
Prejsť na: navigácia, hľadanie
  • Poslednú DÚ odovzdávajte do 16.5. do 22:00
  • V stredu rozcvička na grafy
  • Projekty bude treba odovzdať pravdepodobne do nedele 20.5. 22:00, predvádzanie upresníme
  • Piatok 18.5. o 13:00 v posluchárni B záverečná písomka
  • Termíny skúšok
    • Streda 23.5. 9:00 v H6 (riadny)
    • Štvrtok 7.6. 9:00 v H6 (riadny alebo 1. opravný)
    • Streda 20.6. 9:00 v H6 (1. alebo 2. opravný)
    • Koncom júna bude ešte 2. opravný termín, dátum upresníme neskôr
  • Prípadné konflikty s dátumami písomky alebo skúšok nám dajte vedieť čím skôr
  • Ak by ste chceli nejakú skupinovú konzultáciu pred skúškou alebo testom, dajte nám vedieť

Informácie ku skúške

Orientované grafy

V orientovanom grafe má každá hrana smer (zobrazujeme ako šípku z jedného vrcholu do druhého)

  • napríklad jednosmerné ulice, závislosti medzi úlohami
  • v cestách a cykloch zväčša vyžadujeme, aby išli iba v smere šípky

Pre orientované grafy môžeme využiť existujúci interface Graph ako sme ho mali definovaný pri neorientovaných grafoch.

  • Pri implementácii funkcie addEdge však vložíme hranu iba jedným smerom. Napr. pre hranu (0,1) vložíme 1 medzi susedov 0 ale nie 0 medzi susedov 1.
  • Funkcia existsEdge nám potom pre parametre (0,1) odpovie true ale pre (1,0) odpovie false.
  • Iterátor adjIterator bude poskytovať iba vychádzajúce hrany

Prehľadávanie do hĺbky

V takto implementovanom grafe môžeme použiť prehľadávanie do hĺbky z minulých prednášok na zistenie existencie orientovanej cesty medzi dvoma vrcholmi.

  • Treba si však uvedomiť, že podobne, ako existencia hrany (0,1) nehovorí nič o hrane (1,0) ani existencia cesty medzi dvomi vrcholmi nie je obojsmerná
  • Keďže však máme k dispozícii iterátor cez výstupné hrany, vytvárame práve správne orientované cesty
void search(int vertex, boolean[] visited) {
    visited[vertex] = true;  
    //prejdi cez vchadzajuce hrany
    for (int neighbor: g.adjVertices(vertex)){
        // ak este sused nebol vobec navstiveny, navstiv do rekurzivne
        if (!visited[neighbor]) {
            search(neighbor,visited); // navstivime ho rekurzivne
        }
    }
}
  • Čo ak by sme chceli vypísať cestu z vrcholu u do vrcholu v?
  • Viacnásobným použitím funkcie vieme získať zoznamy vrcholov, ktoré sú dosiahnuteľné z jednotlivých vrcholov.

Cvičenie:

  • Zamyslite sa, čo by robil algoritmus na hľadanie komponentov z prednášky 33 na orientovanom grafe - funguje? prečo?

Prehľadávanie do šírky a najkratšie cesty v neohodnotenom orientovanom grafe

Podobne ako prehľadávanie do hĺbky aj prehľadávanie do šírky je na orientovanom (neohodnotenom) grafe rovnako použiteľné.

  • Získame najkratšie orientované cesty z vrchola do všetkých ostatných vrcholov
  • Môžeme si hrany rozdeliť na stromové (ktoré objavili vrchol) a ostatné

Je orientovaný graf strom?

Orientovaný graf je strom práve vtedy, keď

  • má práve jeden koreň, do ktorého nevchádza žiadna hrana
  • z koreňa je možné dosiahnuť všetky ostatné vrcholy
  • do každého vrcholu okrem koreňa vchádza práve jedna hrana

Ako by sme presne implementovali v našom interface Graph?

  • napíšte metódu, ktorá do poľa pre každý vrchol orientovaného grafu spočíta, koľko hrán do neho vstupuje

Topologické triedenie, existencia cyklu

Motivačná úloha:

  • Na úrade potrebujeme vybaviť niekoľko potvrdení. Ale číha tam na nás byrokracia: o niektorých dvojiciach potvrdení vieme, že na získanie potvrdenia B potrebujeme predložiť potvrdenie A.
  • Úlohou je nájsť poradie (a zistiť, či také vôbec existuje) ako potvrdenia na úrade vybavovať.
  • Úlohu reprezentujeme ako orientovaný graf, kde vrcholy sú potvrdenia a hrany závislosti medzi nimi.

Topologické usporiadanie orientovaného grafu je permutácia jeho vrcholov v_{1},v_{2},\dots v_{n} taká, že pre každú hranu (v_{i},v_{j}) platí, že i<j

  • t.j. všetky hrany idú v permutácii zľava doprava
  • orientovaný graf môže mať aj viac ako jedno topologické usporiadanie
    • Koľko najviac topologických usporiadaní môže mať orientovaný graf s n vrcholmi? Pre aký graf sa to stane?
  • Môže sa však stať, že graf nemá žiadne topologické usporiadanie
    • To sa stane práve vtedy, ak je v grafe orientovaný cyklus
    • Zjavne ak je v grafe orientovaný cyklus, topologické usporiadanie neexistuje, lebo v topologickom usporiadaní idú hrany zľava doprava a cyklus sa nemá ako vrátiť späť
    • Skúste si dokázať aj opačnú implikáciu
    • Graf bez cyklu voláme acyklický


Samotné topologické triedenie bude pracovať nasledovne:

  • ak máme vrchol, do ktorého nevchádza žiadna hrana, môžeme ho vypísať (potvrdenie, ktoré nemá žiadne závislosti)
  • z tohto vrcholu vychádzajú hrany, môžeme ich odteraz ignorovať (splnené závislosti)
  • pre každý vrchol si pamätáme počet zatiaľ nesplnených závislostí
    • na začiatku to bude počet hrán vchádzajúcich do vrchola
    • keď vypíšeme vrchol v, prejdeme všetky hrany z neho vychádzajúce a vrcholom na druhom konci znížime počet nesplnených závislostí
  • udržujeme si tiež množinu vrcholov, ktoré už nemajú nesplnené závislosti a v každom kroku jeden vrchol z nej vyberieme a vypíšeme
 
    /* Statická metóda, ktorá dostane orientovaný acyklický graf 
     * a vráti zoznam jeho vrcholov
     * v topologickom usporiadaní */
    public static ArrayList<Integer> TopologicalSort(Graph g) {
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu

        // inicializuj pocet nesplnenych zavislosti, potom
        // prejdi vsetky hrany a zvysuj
        int[] numberOfPrerequisites = new int[n];
        for (int vertex = 0; vertex < n; vertex++) {
            numberOfPrerequisites[vertex] = 0;
        }
        for (int vertex = 0; vertex < n; vertex++) {
            for (int neighbor : g.adjVertices(vertex)) {
                numberOfPrerequisites[neighbor]++;
            }
        }

        // vsetky vrcholy bez zavislosti pridaj do mnoziny ready
        LinkedList<Integer> ready = new LinkedList<Integer>();
        for (int vertex = 0; vertex < n; vertex++) {
            if (numberOfPrerequisites[vertex] == 0) {
                ready.add(vertex);
            }
        }

        // inicializuj vysledok
        ArrayList<Integer> order = new ArrayList<Integer>();  
        // hlavny cyklus - vyberaj vrchol z mnoziny ready a pridavaj do order
        while (!ready.isEmpty()) {
            int vertex = ready.remove();
            order.add(vertex);
            // pre susedov vypisaneho vrchola zniz pocet zavislosti
            for (int neighbor : g.adjVertices(vertex)) {
                numberOfPrerequisites[neighbor]--;
                // ak to bola posledna zavislost, vrchol je uz vypisatelny
                if (numberOfPrerequisites[neighbor] == 0) {
                    ready.add(neighbor);
                }
            }
        }
        return order;
    }

Čo spraví tento program, ak mu dáme vstupný graf, v ktorom je orientovaný cyklus?

Ak sa nám do poľa order podarilo dať všetky vrcholy, máme topologické usporiadanie, graf je teda acyklický

  • ak máme v poli order menej ako n vrcholov, každý vrchol má aspoň jednu nesplnenú závislosť
  • topologické triedenie teda v tomto prípade nemôže existovať (žiaden vrchol nemôže ísť prvý)
  • graf má teda cyklus

Cvičenie:

  • Upravte program tak, aby v prípade, že graf má orientovaný cyklus, funkcia TopologicalSort vrátila null
  • Napíšte program, ktorý v prípade, že graf nie je acyklický, v ňom nájde orientovaný cyklus.

Existencia cyklu a topologické triedenie pomocou prehľadávania do hĺbky

Trochu iný prístup založený na malej modifikácii prehľadávania do hĺbky, ale ťažšie vidieť, že funguje (dobré precvičenie)

Do prehľadávania do hĺbky pridáme pole finished

  • keď začneme rekurziu pre vrchol v, nastavíme visited[v]=true (ako predtým)
  • keď končíme rekurziu pre vrchol v, nastavíme finished[v]=true

V danom bode behu algoritmu máme vrcholy troch typov:

  • ešte nenavštívené, visited[v] aj finished[v] je false
  • už ukončené, visited[v] aj finished[v] je true
  • rozrobené, visited[v] je true, ale finished[v] je false

Rozrobené vrcholy sú všetky na zásobníku a sú spojené orientovanou cestou

Topologické triedenie:

  • Vždy keď nastavíme finished[v]=true, pridáme v do poľa order
  • Po prehľadaní celého grafu otočíme poradie poľa order

Predstavme si, že kontrolujeme hrany vychádzajúce z vrchola v, ktorý je teste pred dokončením, t.j. po tom, ako sme pozreli jeho susedov, ale predtým ako sme ho dali do poľa order. Kam môžu ísť?

  • Do ešte nenavštíveného vrchola u. To sa nestane, lebo by sme predtým zavolali rekurziu pre u.
  • Do ukončeného vrchola u. Ten už je v poli order, ale v tam ešte nie je. Hrana (u,v) teda pôjde vo výsledku zľava doprava.
  • Do rozrobeného vrchola u. Toto ale znamená existenciu cyklu v grafe, takže topologické triedenie neexistuje.
class TopologicalSort {

    /** Samotny graf */
    private Graph g;
    /** Zoznam vrcholov v topologickom usporiadani */
    private ArrayList<Integer> order;
    /** Indikator, ci je graf acyklicky  */
    private boolean acyclic;
    /** Pole indikujuce, ci sme uz vrchol v prehladavani navstivili */
    private boolean[] visited;
    /** Pole indikujuce, ci sme uz ukoncili prehladavanie vrchola
     * a vsetkych jeho nasledovnikov */
    private boolean[] finished;

    /** Konstruktor, ktory dostane graf a prehladavanim do hlbky
     * testuje acyklickost grafu a hlada topologicke usporiadanie */
    public TopologicalSort(Graph g) {
        this.g = g;  // uloz graf
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu

        order = new ArrayList<Integer>();  // inicializuj vysledok
	acyclic = true;      // zatial sme nevideli cyklus

	visited = new boolean[n];
        finished = new boolean[n];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
            finished[i] = false;
        }
        // prechadzaj cez vrchol a ak najdes nevyfarbeny,
        // spusti prehladavanie 
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                search(i);
            }
        }
        Collections.reverse(order); //prevratime poradie vrcholov
    }
    

    /** Pomocna rekurzivna metoda pouzivana v konstruktore 
     * na vyfarbenie vsetkych nasledovnikov vrchola vertex */
    private void search(int vertex) {
        visited[vertex] = true;  // uz sme ho navstivili
        //prejdi cez vychadzajuce hrany
        for (int neighbor: g.adjVertices(vertex)){
            // ak uz sme suseda navstivili, ale este nie je
            // ukonceny, mame cyklus
            if (visited[neighbor] && !finished[neighbor]) {
                acyclic = false;
            }
            // ak este sused nebol vobec navstiveny, navstiv do rekurzivne
            if (!visited[neighbor]) {
                search(neighbor); // navstivime ho rekurzivne
            }
        }
        // ukoncili sme prehladavanie aktualneho vrcholu
        // poznac ako ukonceny a pridaj ho do zoznamu
        finished[vertex] = true;
        order.add(vertex);
    }
    ...
}

Zdrojový kód programu, topologické triedenie 1

Pomocou počítania závislostí

package prog;

import java.io.*;
import java.util.*;

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

/** Trieda reprezentujúca orientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return adjLists.size();
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v jednom smere
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        // vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex)); 
    }
}

/** Trieda obsahujuca topologicke usporiadanie vrcholov orientovaneho grafu */
class TopologicalSort {

    /** samotny graf */
    private Graph g;
    /** Zoznam vrcholov v topologickom usporiadani */
    private ArrayList<Integer> order;
    /** Indikator, ci je graf acyklicky  */
    private boolean acyclic;

    /** Konstruktor, ktory dostane graf a prehladavanim do hlbky
     * testuje acyklickost grafu a hlada topologicke usporiadanie */
    public TopologicalSort(Graph g) {
        this.g = g;  // uloz graf
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu

	// inicializuj pocet nesplnenych zavislosti, potom 
	// prejdi vsetky hrany a zvysuj
        int[] numberOfPrerequisites = new int[n];
        for (int vertex = 0; vertex < n; vertex++) {
            numberOfPrerequisites[vertex] = 0;
        }
        for (int vertex = 0; vertex < n; vertex++) {
	    for (int neighbor: g.adjVertices(vertex)){	    
		numberOfPrerequisites[neighbor]++;
	    }
	}

	// vsetky vrcholy bez zavislosti pridaj do mnoziny ready
	LinkedList<Integer> ready = new LinkedList<Integer>();
        for (int vertex = 0; vertex < n; vertex++) {
            if(numberOfPrerequisites[vertex] == 0) {
		ready.add(vertex);
	    }
	}

        order = new ArrayList<Integer>();  // inicializuj vysledok
	// hlavny cyklus - vyberaj vrchol z mnoziny ready a pridavaj do order
	while (!ready.isEmpty()){   
	    int vertex = ready.remove();
	    order.add(vertex);
	    // pre susedov vypisaneho vrchola potrebujem znizit pocet zavislosti
	    for (int neighbor : g.adjVertices(vertex)){
		numberOfPrerequisites[neighbor]--;
		// ak to bola posledna zavislost, vrchol je uz vypisatelny
		if(numberOfPrerequisites[neighbor]==0) {
		    ready.add(neighbor);
		} 
	    }
        }

        acyclic = (order.size()==n);
    }
    
    /** vratil, ci je vstupny graf acyklicky */
    public boolean isAcyclic() {
        return acyclic;
    }

    /** ak je graf acyklicky, vrati topologicke usporiadanie vrcholov */
    public ArrayList<Integer> order() {
        if (!acyclic) {
            return null;
        }
        return new ArrayList<Integer>(order);
    }
}

public class Prog {

    /** Zo scannera s načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov.
     * Uloží ho ako AdjMatrixGraph. */
    static Graph readGraph(Scanner s) {
        int n = s.nextInt();
        int m = s.nextInt();
        Graph g = new AdjListsGraph(n);
        for (int i = 0; i < m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            g.addEdge(u, v);
        }
        return g;
    }
    

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        Graph g = readGraph(s);
        s.close();
      
        TopologicalSort sort = new TopologicalSort(g);
        if (sort.isAcyclic()) {
            System.out.println("Topologicke usporiadanie: " + sort.order());
        } else {
            System.out.println("Graf ma cyklus");
        }
    }
}
/** Priklad vstupu bez cyklu:

4 4
1 0
2 0
2 1
3 1

 *  s cyklom:
4 4
1 0
0 2
2 1
3 1

 */

Zdrojový kód programu, topologické triedenie 2

Pomocou prehľadávania do hĺbky

package prog;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.Collections;

/** Interface reprezentujúci graf s n vrcholmi očíslovanými 0..n-1. */
interface Graph {

    /** Vráti počet vrcholov grafu n. */
    int getNumberOfVertices();

    /** Vráti počet hrán grafu. */
    int getNumberOfEdges();

    /** Do grafu pridá hranu z vrcholu from do vrcholu to,
     * vráti true ak sa ju podarilo pridať. */
    boolean addEdge(int from, int to);

    /** Vráti true, ak existuje hrana z vrcholu from
     * do vrcholu to. */
    boolean existsEdge(int from, int to);

    /** Vráti iterovateľnú skupinu susedov vrchola vertex.
     * V prípade orientovaného grafu vracia iba hrany vychádzajúce z vrchola.
     * Metóda remove iterátora nemusí byť podporovaná. */
    Iterable<Integer> adjVertices(int vertex);
}

/** Trieda reprezentujúca orientovaný graf pomocou
 * zoznamov susedov uložených v poli dynamickej dĺžky (ArrayList). */
class AdjListsGraph implements Graph {

    /** Zoznam susedov pre každý vrchol */
    private ArrayList<ArrayList<Integer>> adjLists;
    /** Počet hrán v grafe */
    private int numEdges;

    /** Konštruktor dostane počet vrcholov grafu */
    public AdjListsGraph(int numVertices) {
        adjLists = new ArrayList<ArrayList<Integer>>(numVertices);
        for (int i = 0; i < numVertices; i++) {
            adjLists.add(new ArrayList<Integer>());
        }
        numEdges = 0;
    }

    @Override
    public int getNumberOfVertices() {
        return adjLists.size();
    }

    @Override
    public int getNumberOfEdges() {
        return numEdges;
    }

    @Override
    public boolean addEdge(int from, int to) {
        adjLists.get(from).add(to); // pridaj hranu v jednom smere
        numEdges++;
        return true;
    }

    @Override
    public boolean existsEdge(int from, int to) {
        return adjLists.get(from).contains(to); // pozri do zoznamu susedov pre from
    }

    @Override
    public Iterable<Integer> adjVertices(int vertex) {
        // vrati ArrayList obaleny, aby sa nedal menit
        return Collections.unmodifiableList(adjLists.get(vertex)); 
    }
}

/** Trieda obsahujuca topologicke usporiadanie vrcholov orientovaneho grafu */
class TopologicalSort {

    /** samotny graf */
    private Graph g;
    /** Zoznam vrcholov v topologickom usporiadani */
    private ArrayList<Integer> order;
    /** Indikator, ci je graf acyklicky  */
    private boolean acyclic;
    /** Pole indikujuce, ci sme uz vrchol v prehladavani navstivili */
    private boolean[] visited;
    /** Pole indikujuce, ci sme uz ukoncili prehladavanie vrchola
     * a vsetkych jeho nasledovnikov */
    private boolean[] finished;

    /** Konstruktor, ktory dostane graf a prehladavanim do hlbky
     * testuje acyklickost grafu a hlada topologicke usporiadanie */
    public TopologicalSort(Graph g) {
        this.g = g;  // uloz graf
        int n = g.getNumberOfVertices();  // pocet vrcholov grafu

        order = new ArrayList<Integer>();  // inicializuj vysledok
        acyclic = true;  // zatial sme nevideli cyklus

	visited = new boolean[n];
        finished = new boolean[n];
        for (int i = 0; i < n; i++) {
            visited[i] = false;
            finished[i] = false;
        }
        // prechadzaj cez vrchol a ak najdes nevyfarbeny,
        // spusti prehladavanie 
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                search(i);
            }
        }
	Collections.reverse(order); //prevratime poradie vrcholov
    }
    

    /** Pomocna rekurzivna metoda pouzivana v konstruktore 
     * na vyfarbenie vsetkych nasledovnikov vrchola vertex */
    private void search(int vertex) {
        visited[vertex] = true;  // uz sme ho navstivili
        //prejdi cez vychadzajuce hrany
        for (int neighbor: g.adjVertices(vertex)){
            // ak uz sme suseda navstivili, ale este nie je
            // ukonceny, mame cyklus
            if (visited[neighbor] && !finished[neighbor]) {
                acyclic = false;
            }
            // ak este sused nebol vobec navstiveny, navstiv do rekurzivne
            if (!visited[neighbor]) {
                search(neighbor); // navstivime ho rekurzivne
            }
        }
        // ukoncili sme prehladavanie aktualneho vrcholu
        // poznac ako ukonceny a pridaj ho do zoznamu
        finished[vertex] = true;
        order.add(vertex);
    }

    /** vratil, ci je vstupny graf acyklicky */
    public boolean isAcyclic() {
        return acyclic;
    }

    /** ak je graf acyklicky, vrati topologicke usporiadanie vrcholov */
    public ArrayList<Integer> order() {
        if (!acyclic) {
            return null;
        }
        return new ArrayList<Integer>(order);
    }
}

public class Prog {

    /** Zo scannera s načíta graf vo formáte: počet vrcholov,
     * počet hrán a zoznam hrán zadaných koncami vrcholov.
     * Uloží ho ako AdjMatrixGraph. */
    static Graph readGraph(Scanner s) {
        int n = s.nextInt();
        int m = s.nextInt();
        Graph g = new AdjListsGraph(n);
        for (int i = 0; i < m; i++) {
            int u = s.nextInt();
            int v = s.nextInt();
            g.addEdge(u, v);
        }
        return g;
    }
    

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);
        Graph g = readGraph(s);
        s.close();
      
        TopologicalSort sort = new TopologicalSort(g);
        if (sort.isAcyclic()) {
            System.out.println("Topologicke usporiadanie: " + sort.order());
        } else {
            System.out.println("Graf ma cyklus");
        }
    }
}
/** Priklad vstupu bez cyklu:

4 4
1 0
2 0
2 1
3 1

 *  s cyklom:
4 4
1 0
0 2
2 1
3 1

 */