package euler;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

//trida vrchol
class top {
    int index;
    char color;
    int before;
    top(int index){
        this.index = index;
        this.before = -1;
    }
}

//trida Graph
class Graph{
    String graphName;
    int[][] matrix;
    int arrayLength;
    top[] topArray;
    int[] visited;
    int last=0;
    List<Integer> path = new ArrayList<Integer>();
    
    //konstruktor tridy graph - build - in graph
    Graph(int type){
        if (type == 1) {
            init("rohlik", 3);
            //naplneni matice
            this.matrix[1] = new int[] { -1, 0, 1, 0 };
            this.matrix[2] = new int[] { -1, 1, 0, 1 };
            this.matrix[3] = new int[] { -1, 0, 1, 0 };
        }
        if (type == 2) {
            init("domecek", 5);
            //naplneni matice
            this.matrix[1]=new int[] {-1, 0, 0, 1, 0, 1};
            this.matrix[2]=new int[] {-1, 0, 0, 1, 0, 1};
            this.matrix[3]=new int[] {-1, 1, 1, 0, 1, 1};
            this.matrix[4]=new int[] {-1, 0, 0, 1, 0, 1};
            this.matrix[5]=new int[] {-1, 1, 1, 1, 1, 0};            
        }
        
        if (type == 3) {
            init("orientovana dvounoha", 5);
            //naplneni matice
            this.matrix[1]=new int[] {-1, 0, 0, 1, 0, 0};
            this.matrix[2]=new int[] {-1, 1, 0, 0, 0, 1};
            this.matrix[3]=new int[] {-1, 0, 1, 0, 1, 0};
            this.matrix[4]=new int[] {-1, 0, 0, 1, 0, 0};
            this.matrix[5]=new int[] {-1, 0, 1, 0, 0, 0};                                              
        }
        
        if (type == 4) {
            init("pazour", 5);
            //naplneni matice
            this.matrix[1]=new int[] {-1, 0, 0, 1, 0, 0};
            this.matrix[2]=new int[] {-1, 1, 0, 0, 0, 0};
            this.matrix[3]=new int[] {-1, 0, 1, 0, 1, 0};
            this.matrix[4]=new int[] {-1, 0, 0, 1, 0, 0};
            this.matrix[5]=new int[] {-1, 0, 0, 0, 0, 0};                                              
        }
    }    
    
    // konstruktor tridy graph - mozno zadat delku a jmeno
    Graph(String graphName, int topCount){
        init(graphName, topCount);
    }
    
    // vraci pocet vrcholu
    int getTopCount() {
        return arrayLength - 1;   
    }
    
    // inicializuje graf zadanym jmenem a poctem vrcholu
    void init(String graphName, int topCount) {
        this.graphName=graphName;
        this.arrayLength=topCount+1;
        this.matrix=new int[topCount+1][topCount+1];
        initTops();
    }
    
    void initTops() {
        this.topArray=new top[arrayLength];
        this.visited=new int[arrayLength];
        for( int i = 1; i < arrayLength; i++ ){          
            topArray[i] = new top(i); 
            topArray[i].color = 'W';
        }
    }
    
    //naplni matici souslednosti
    void putNeighbours(){
        System.out.println("Definujte hrany usporadanych dvojic(0=neexistuje, 1=existuje)");
        for ( int r = 1; r < arrayLength; r++ ){
            for ( int s = 1; s < arrayLength; s++ ){
                if (r!=s){
                    System.out.print(r + " -> " + s +": " );
                    matrix[r][s]=VstupData.ctiInt();
                }else{matrix[r][s]=0;}
            }
        }
    }
    
    void matrixPrintf(){	
        for ( int r = 1; r < arrayLength; r++ ){
            for ( int s = 1; s < arrayLength; s++ ){
                System.out.print(matrix[r][s]+" ");
            }
            System.out.println();
        }
    }
    
    //vraci index dalsiho souseda
    int nextNeigbour( int r,int s ){
        s++;												
        if ( s < arrayLength ){			
            while(matrix[r][s]==0 ){ 						
                s++;
                if (s==arrayLength){return(-1);}
            }
            return(s);														
        }else{return(-1);}									
    }   
    
    // prohledavani do hloubky od vrcholu s, vraci pocet navstivenych vrcholu
    int searchDFS (int s) {
        // inicializace obarveni vrcholu
        initTops();        
        return searchDFSRecurse(s);
    }
    
    //prohledavani do hloubky DFS
    int searchDFSRecurse (int s) {
        int result = 1;
        topArray[s].color = 'G';
        path.add(Integer.valueOf(s));
        int neighbour = nextNeigbour(s,0);					
        
        while ( neighbour!=(-1) ) {							
            if (topArray[neighbour].color == 'W') {
                result += searchDFSRecurse(neighbour);                          
            }            
            neighbour = nextNeigbour(s,neighbour);               
        }
        topArray[s].color = 'B';
        path.remove(Integer.valueOf(s));
        return result;
    }
    
    // prohledava graf do hloubky od zadaneho vrcholu, vraci prvni nalezenou kruznici
    List<Integer> searchDFSCircle(int s) {
        // inicializace obarveni vrcholu
        initTops();
        // vycisteni navratove cesty
        path.clear();
        return searchDFSCircleRecurse(s, -1);
    }
    
    
    // odstrani hrany kruznice z grafu
    void removeCircle(List<Integer> circle, boolean oriented) {
        for (int i = 0; i < circle.size() - 1; i++) {
            int from = circle.get(i).intValue();
            int to = circle.get(i+1).intValue();            
            matrix[from][to] = 0;
            // pokud se nejedna o orientovany graf, odstranujeme oba smery
            if (!oriented) {                
                matrix[to][from] = 0;
            }
        }        
    }
    
    // vrati vsechny sousedy daneho vrcholu, pripadneho predchudce da na konec
    List<Integer> getNeighbours(int s, int before) {
        List<Integer> result = new ArrayList<Integer>();
        for (int i = 1; i < arrayLength; i++) {
            if (matrix[s][i] == 1 && i != before) {
                result.add(Integer.valueOf(i));
            }
        }
        // dej predchudce na konec
        if (before != -1 && matrix[s][before] == 1) {
            result.add(Integer.valueOf(before));
        }
        return result;
    }
    
    // prohledavani do hloubky DFS, vrati prvni kruznici na kterou narazi
    List<Integer> searchDFSCircleRecurse(int s, int before) {
        // obarvi na sedo
        topArray[s].color = 'G';
        // drzi si cestu od pocatecniho vrcholu (pro zpetne sestaveni cesty)
        path.add(Integer.valueOf(s));
        // projdi vsechny sousedy 
        List<Integer> neighbours = getNeighbours(s, before);
        for (Integer neighbour : neighbours) {
            int n = neighbour.intValue();
            // pokud je dany soused sedy, nalezli jsme reverzni hranu - mame kruznici
            if (topArray[n].color == 'G') {
                // nalezneme jeji zacatek ve zpatecni ceste
                int circleStart = path.indexOf(Integer.valueOf(n));
                // a ulozime si ji do noveho pole
                List<Integer> newCircle = new ArrayList<Integer>();
                for (int i = circleStart; i < path.size(); i ++) {
                    newCircle.add(path.get(i));
                }
                newCircle.add(Integer.valueOf(n));
                // ktere vratime jako vysledek
                return newCircle;
            }
            // pokud je dany soused bily, pokracujeme v rekurzi
            if (topArray[n].color == 'W') {
                return searchDFSCircleRecurse(n, s);
            }            
        }
        // uz nemame dalsi sousedy, obarvime na cerno
        topArray[s].color = 'B';
        // a odstranime vrchol ze zpatecni cesty
        path.remove(Integer.valueOf(s));
        return null;
    }
    
    // pokusi se nalezt vsechny kruznice, vrati je jako seznam seznamu vrcholu
    List<List<Integer>> findAllCircles(boolean oriented) {
        List<List<Integer>> circles = new ArrayList<List<Integer>>();
        // pro kazdy vrchol
        for (int i = 1; i < arrayLength; i ++) {            
            List<Integer> circle = null;
            // se pokus najit vsechny kruznice
            while ((circle = searchDFSCircle(i)) != null) {
                // ktere si uloz
                circles.add(circle);
                // a odstran je z grafu
                removeCircle(circle, oriented);
            }
        }
        return circles;        
    }
    
    // testuje, zda je dany graf neorientovany
    boolean isUnOriented() {        
        for ( int r = 1; r < arrayLength; r++ ){
            for ( int s = 1; s < arrayLength; s++ ){
                if (matrix[r][s] != matrix[s][r]) {
                    return false;
                }
            }
        }
        return true;
    }
    
    // vraci true, pokud je graf eulerovsky
    boolean isEuler(boolean oriented) {
        if (oriented) {
            for (int i = 1; i < arrayLength; i++) {
                if (getTopDegreeInput(i) != getTopDegreeOutput(i)) {
                    return false;
                }
            }
            return (searchDFS(1) == getTopCount());            
        }
        if (!isUnOriented()) {
            throw new IllegalStateException("Graph is not unOriented.");
        }
        for (int i = 1; i < arrayLength; i++) {
            if ((getTopDegreeInput(i) % 2) != 0) {
                return false;
            }
        }
        return (searchDFS(1) == getTopCount());            
        
    }
    
    // vraci vystupni stupen vrcholu
    int getTopDegreeOutput(int top) {
        int result = 0;
        for (int i = 1; i < arrayLength; i++) {
            result += matrix[top][i];
        }
        return result;
    }
    
    // vraci vstupni stupen vrcholu
    int getTopDegreeInput(int top) {
        int result = 0;
        for (int i = 1; i < arrayLength; i++) {
            result += matrix[i][top];
        }
        return result;
    }
    
    // najde eulerovsky tah
    List<Integer> getEulerTah(boolean oriented) {
        if (!isEuler(oriented)) {
            System.out.println("Graf neni eulerovsky.");
            return new ArrayList<Integer>();
        }
        // ze vsech kruznic se pokusi sestavit eulerovsky tah
        List<List<Integer>> circles = findAllCircles(oriented);
        // vypis nalezene kruznice
        System.out.println("Byly nalezeny nasledujici kruznice: " + circles);
                
        // dokud mame alespon jednu kruznici
        while (circles.size() > 1) {
            // vezmu prvni na rade
            List<Integer> firstCircle = circles.remove(0);        
            // a pokusim se ji rozsirit o nejakou dalsi
            List<Integer> biggerCircle = new ArrayList<Integer>();        
            // takze pro kazdy vrchol prvni kruznice
            for (int i = 0; i < firstCircle.size(); i++) {
                Integer top = firstCircle.get(i);
                biggerCircle.add(top);
                // zkusim najit mezi ostatnimi nejakou, ktera ma shodny pocatecni a koncovy vrchol s touto prvni
                for (Iterator<List<Integer>> c = circles.iterator(); c.hasNext(); ) {
                    List<Integer> circle = c.next();
                    // pokud takovou naleznu
                    if (circle.get(0).equals(top)) {
                        // rozsirim prvni kruznici o nalezenou
                        biggerCircle.addAll(circle.subList(1,circle.size()));
                        // a tuto kruznici pote odstranim
                        c.remove();
                    }
                }             
            }
            // rozsirenou kruznici pak pridam nakonec seznamu, aby se dostala rada i na ostatni :-)
            circles.add(biggerCircle);
        }
        // kdyz zbyva jiz jen jedna kruznice, vratim ji, jedna se o eulerovsky tah
        return circles.get(0);            
    }    
    
}			

public class EuleruvTah {

	public static void checkGraph(Graph testGraph,boolean oriented){
		if (!testGraph.isEuler(oriented)) {
            System.out.println("Graf neni eulerovsky.");
        }
        else {
            System.out.println();                 
            System.out.println("Nalezeny eulerovsky tah: " + testGraph.getEulerTah(oriented));             
        }               
    }

	public static void main( String[] args ) {	
    	
		// Nageneruj si graf	
		// Predvybrane jsou 1,2,3,4
    	Graph testGraph = new Graph(3);          

//		Alternativne jde zadat z klavesnice
//    	Graph testGraph = new Graph("Zadany",5);
//    	testGraph.putNeighbours();
    	
    	// Pro kontrolu vytiskni jeho matici
    	testGraph.matrixPrintf();
    	//Otestuj ze splnuje podminky (je eulerovsky) a pokud ano, najdi tah
    	//Druhy parametr udava orientovanost
    	//true - orientovany
    	//false - neorientovany
    	checkGraph(testGraph,true);
        
	} 
}