package course;

import java.util.Stack;

/**
 * <p>Title: 拓撲排序</p>
 *
 * <p>Description: 實現拓撲排序</p>
 *
 * <p>Copyright: Copyright (c) 2007 </p>
 *
 * <p>Company: www.bchine.com</p>
 *
 * @author 李丕績
 * @version 1.0
 */
public class Topological extends Adjacency {
    Stack S = new Stack();
    Adjacency ad = new Adjacency();
    Field fi[];
    Field eld = new Field();


    public static int t;

    public boolean Topo(Field v[], int n, int aa[][]) {
        fi=new Field[ n];
        ad.InitializePos(n); //初始化數組pos作為中間橋梁的作用
        int InDegree[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            InDegree[i] = 0; //初始化入度

        }
        for (int i = 1; i <= n; i++) {
            int u = ad.Begin(i, aa);
            System.out.println(u + "a");

            while (u != 0) {
                InDegree[u]++;
                u = NextVertex(i, aa);
                System.out.println(u + "b");
            }
        }

        for (int i = 1; i <= n; i++) {
             fi[i-1]=new Field() ;
            if (InDegree[i] == 0) {
                fi[i-1].index = i;
                fi[i-1].term = 1;
                System.out.println(fi[i-1].index + "入棧");
                S.push(fi[i-1]);

                }

        }




      int a= 0;
        while (!S.empty()) {
           eld = (Field) S.pop();
            v[a++] = eld;
            int w = eld.index;
            System.out.println(w + "出棧");
            int u = Begin(w, aa);
            while (u != 0) {
                InDegree[u]--;
                if (InDegree[u] == 0) {
                    fi[u-1].index = u;
                    fi[u-1].term =eld.term + 1;
                    System.out.println(u + "入棧");
                    S.push(fi[u-1]);
                }
                u = NextVertex(w, aa);
            }
        }
        return (a == n);
    }

    public static void main(String[] args) {
        Topological top = new Topological();
    }
}