//trida reprezentuje souseda
class topNeighbour{
	int top;
	topNeighbour next;
	topNeighbour (int v){
		top = v;
		next = null;
	}
}

// trida reprezentuje vrchol
class topS{
	//Barva vrcholu, W=bila(white), G=seda(gray), B=cerna(black)
	char color;
	int index;
	int parent;
	int lenght;
	topNeighbour neighbour;
	
	//kostruktor vrcholu
	topS(int index){
		this.index=index;
		this.color='W';
		neighbour=null;
	}

	//novy soused
	void neighbourNew(int v){
		topNeighbour isNew = new topNeighbour(v);
		if (this.neighbour==null){
			this.neighbour=isNew;
		}
		else{
			topNeighbour j=this.neighbour;
			while (j.next!=null){
				j=j.next;
			}
			j.next=isNew;
		}
	}
	
	//vytisteni seznamu sousedu
	void neighbourPrintf(){
		topNeighbour i;
		if (this.neighbour!=null){
			i=this.neighbour;
			while (i!=null){
				System.out.print(i.top + " ");
				i = i.next;
			}
			System.out.println();
		}
		else {
			System.out.println("Nema sousedy");
		}
	}
}

//trida graph 
class graphS{
	String graphName;
	int arrayLenght;
	topS[] topArray;
	int[] visited;
	int last=0;
	
	//konstruktor s cvicnymi daty
	graphS(){
		int topCount=3;
		this.graphName="testGraph";
		this.arrayLenght=topCount+1;
		this.topArray=new topS[topCount+1];
		this.visited=new int[topCount+1];		
		for (int i=1; i<=topCount; i++){
			topArray[i]=new topS(i);
		}
		//cvicny graph naplneny hranami			
		topArray[1].neighbourNew(2);
		topArray[1].neighbourNew(3);
		topArray[3].neighbourNew(1);
	}

	//konstruktor umoznujici zadat jmeno a pocet vrcholu
	graphS(String graphName,int topCount){
		this.graphName=graphName;
		this.arrayLenght=topCount+1;
		this.topArray=new topS[topCount+1];
		this.visited=new int[topCount+1];		
		for (int i=1; i<=topCount; i++){
			topArray[i]=new topS(i);
		}
	}

	//nacti hrany z klavesnice
	void read(){
		int x;		
		for (int i = 1; i < topArray.length; i++ ){
		System.out.println("Zadej sousedy vrcholu "+ i +", 0=konec");
			while (true) {
				x = VstupData.ctiInt();
				if ( x != 0 ){
					topArray[i].neighbourNew(x);
				}
				else {
					break;
				}
			}
		}
	}	
	
	//vypise seznam sousednosti grafu
	void write(){
		for (int i = 1; i < topArray.length; i++ ){
			System.out.print( i + " -> " );	
			topArray[i].neighbourPrintf();
		}
	}


	//prohledavani do sirky BFS
	void searchBFS (int s){
		visited[1] = s; 
		last = 1;
		System.out.print(s+" ");
		intFrontaSpoj f = new intFrontaSpoj();
		topArray[s].color = 'W';
		topArray[s].lenght = 0;
		f.push(s);
		while(!f.empty()) {
			int selected = f.pop();	 
			topNeighbour z = topArray[selected].neighbour;			
			while(z != null && topArray[z.top] != null){
			
				if (topArray[z.top].color == 'W') {
					topArray[z.top].color = 'G';
					visited[++last] = z.top;
					System.out.print(z.top + " ");
					f.push(z.top);
				}
				z = z.next;
			}
			topArray[selected].color = 'B';
		}
		System.out.println();
		System.out.println();	
	}		
	
	//prohledavani do hloubky DFS
	void searchDFS (int s) {
		topArray[s].color = 'G';							
		visited[++last] = s;
		System.out.print(s+" ");							
		topNeighbour z = topArray[s].neighbour;					
		while (z != null && topArray[z.top] != null) {
			if (topArray[z.top].color == 'W'){
				searchDFS(z.top);
			}
			z = z.next;
		}	
	topArray[s].color = 'B';                         
	}
}		


public class grafSeznam {
	public static void main( String[] args ) {	

		
//		System.out.println("Zadej Pocet Vrcholu");
//		graphS testGraph = new graphS("pokus",VstupData.ctiInt());  

		graphS testGraph1 = new graphS();  
		graphS testGraph2 = new graphS();  

		
//		testGraph.read();
//		testGraph.write();
		
		System.out.println("Ze ktereho vrcholu hledat?");
		int v=VstupData.ctiInt();
		testGraph1.searchBFS(v);
		testGraph2.searchDFS(v);

	}	
}