1022.cpp

来自「我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2」· C++ 代码 · 共 51 行

//toplogical sort;
#include <iostream>
using namespace std;

const int maxN = 100;
bool map[maxN + 1][maxN + 1];
int deg[maxN + 1];
int ord[maxN + 1];
int n;
void readIn()
{
     int i;
     memset( deg, 0, sizeof(deg) );
     memset( map, 0 , sizeof(map) );
     cin >> n;
     for( i = 1 ; i <= n; i++ )
     {
          int t;
          while (cin >> t, t!= 0) { map[i][t] = true; deg[t] ++; }
     }
     
}

void work()
{
     int i,j,k;
     for( i = 1; i <= n; i++ )
     {
          j = 1;
          while( deg[j] != 0 ) j++;
          deg[j] = -1;
          ord[i] = j;
          for( k = 1; k <= n; k++)
               if(map[j][k]) deg[k]--;
     } 
}
void output()
{
     int i;
     for( i = 1; i <= n; i++ )
          cout << ord[i] << ' ';
     cout << endl;
}
int main()
{
    readIn();
    work();
    output();
    return 0;
}