import java.util.*;
/** 1. Írjuk meg az absztrakt Graph ososztályt. Ez rendelkezzen a következo absztrakt függvényekkel, melyek megvalósitását a származtatott osztályok végzik el: */
abstract class Graph{
/** Egy boolean visszatérésü hasEdge függvény, ami két int tipusú paramétert kap. Akkor tér vissza igazzal, ha létezik él az elso paraméterrel jelzett csúcsból a második paraméterrel jelzett csúcsba. */
abstract boolean hasEdge(int i, int j);

/** Egy számok halmazát visszaadó edgesFrom függvény, amely megadja, hogy a paraméterként kapott csúcsból mely csúcsok érhetoek el. */
abstract Set<Integer> edgesFrom(int i);

/** Egy addEdge függény, amely a gráfhoz hozzáad egy új élt az elso paraméterként kapott csúcsból a második csúcsba. */
abstract void addEdge(int i, int j);

/** 3. A Graph osztályban hozzunk létre egy depthFirstTraversal függvényt, ami a paraméterként kapott csúcsból csinál egy mélységi bejárást, és az eredményét egy listában adja vissza.
Ehhez használjunk stack-ként egy láncolt listát és egy Set-et, amiben számon tartjuk, hogy mely csúcsokat jártuk be.
Kezdetben a stack-ben egy elem van, az a csúcs, amibol a bejárás kiindul. A bejárás addig megy, amig a stack nem üres.
Minden egyes iterációban kivesszük az elso elemét. Ezt az elemet berakjuk az eredménybe és a bejárt csúcsok listájába.
Megnézzük a kivett elembol egy éllel elérheto összes elemet, amit még nem jártunk be és a stack végére füzzük oket. */
LinkedList<Integer> depthFirstTraversal(int x){
	LinkedList<Integer> stack = new LinkedList<>();
	TreeSet<Integer> done = new TreeSet<>();
	LinkedList<Integer> ret = new LinkedList<>();
	stack.add(x);
	int t;
	while(!stack.isEmpty()){
		t=stack.pop();
		if(done.contains(t))continue;
		ret.add(t);
		done.add(t);
		for(int e : edgesFrom(t)){
			stack.push(e);
		}
	}
	//3ICE: Sorrend fontos, ezért ez a konverzió nem jó:
	//return new LinkedList<Integer>(done);
	return ret;
}
}