比较好的一个算法

DAG ：有向无环图。

xmuOJ 选课

一个点的入点（指向它的点怎么表示）怎么表示？数组 or vector？

我最后选择了邻接矩阵。

#include 
    
     #include
     
      #include 
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef queue
           
             Q;int main(){ int N; string name[501]; int a[501][501]; //a[i][j] = 1 则 i指向j int rudu[501]; Q topQ;//top dui lie Q zeroQ; int i,j,k; //initialize memset(a, 0, sizeof(a)); scanf("%d", &N); for (i = 1; i <= N; i++) cin >> name[i]; for (i = 1; i <= N; i++) { scanf("%d", rudu + i); if (rudu[i] == 0) zeroQ.push(i); for ( j = 1; j <= rudu[i]; j++) { int b ; scanf("%d", &b); a[b][i] = 1; } } int top[501], cnt = 0; while (!zeroQ.empty()) { top[++cnt] = zeroQ.front(), zeroQ.pop();// for ( i = 1; i <= N; i++) { if (a[top[cnt]][i] == 1) { if (--rudu[i] == 0) { zeroQ.push(i); } } } } if (cnt!= N) { printf("Impossible!"); return 0; } for (i = 1; i < N; i++) { cout << name[top[i]]; printf(" "); } cout << name[top[N]]; return 0;}/*9Introduction_to_Computer_Science C_Programming_Language Data_Structure Design_and_Analysis_of_Algorithms Mathematical_Analysis Advanced_Algebra Probability_and_Statistics Numerical_Analysis Operating_System01 12 1 23 1 2 3001 52 5 62 1 2*/