/**
 * 鄰接矩陣
 */
public class DenseGraph {
    // 節點數
    private int n;
    // 邊數
    private int m;
    // 是否為有向圖
    private boolean directed;
    // 圖的具體數據
    private boolean[][] g;
    //記錄節點的線數量
    private int[] line;
    //已連接數量
    private int connected;
    //換行專用
    private int lineFeed;
    
    // 構造函數
    public DenseGraph(){
        n = 26;
        m = 0;
        directed = false;
        // g初始化為n*n的布爾矩陣, 每一個g[i][j]均為false, 表示沒有任和線
        g = new boolean[n][n];
        line=new int[n];
    }
    
    //初始化點陣
    private void initialization(){
        //臨時變量，保存每個節點連接節點的數量，以判斷起點
        int count=0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (g[i][j]) {
                    count++;
                }
            }
            line[i]=count;
            count=0;
        }
    }

    // 返回節點個數
    public int V(){ return n;}
    // 返回邊的個數
    public int E(){ return m;}

    // 向圖中添加一個邊
    public void addEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        if( hasEdge( v , w ) )
            return;
        g[v][w] = true;
        if( !directed )
            g[w][v] = true;
        m ++;
    }

    // 驗證圖中是否有從v到w的邊
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
    
    //開始運行
    public void start(){
        //初始化
        this.initialization();
        //輸出鄰接矩陣
        this.print();
        //尋找起點
        int qsd=-1;
        for (int i = 0; i < line.length; i++) {
            if (line[i]%2!=0){
                qsd=i;
                break;
            }else if (line[i]!=0){
                qsd=i;
            }
        }
        //從起點開始回溯尋找路線
        flashBack(qsd);
    }

    public boolean flashBack(int a){
        //如果已經走過的線數量等於總線數量，說明尋路完成
        if (connected==m){
            System.out.print("路線:["+a+"] -> ");
            return true;
        }else {
            //遍歷此點與全部節點的關係並按照以下執行
            //1.如果兩點之間有連接，假設此路線為正確路線，將此線改變為無連接，並開始從此點遍歷
            //2.如果最終無法走過全部線，則確定此路線不正確，回溯並將此線還原為連接，繼續遍歷
            for (int i = 0; i < n; i++) {
                if (g[a][i]){
                    g[a][i]=false;
                    g[i][a]=false;
                    connected++;
                    if (flashBack(i)){
                        lineFeed++;
                        if (lineFeed%20==0)
                            System.out.println();
                        System.out.print("["+a+"] -> ");
                        return true;
                    }else {
                        connected--;
                        g[a][i]=true;
                        g[i][a]=true;
                    }
                }
            }
            return false;
        }
    }

    //輸出鄰接矩陣
    public void print(){
        System.out.println("邊共:"+m+"條");
        System.out.print("鄰接矩陣 ");
        for (int i = 1; i < n; i++) {
            System.out.print(i+"   \t");
        }
        System.out.println();
        for (int i = 1; i < n; i++) {
            System.out.print(i+" \t");
            for (int j = 1; j < n; j++) {
                System.out.print(g[i][j]+" \t");
            }
            System.out.println();
        }
    }
}