Занятие 18

Топологическая сортировка

int n; // число вершин
int connect[N][N]; // дуги и их ориентация
int used[N]; // флаг, что вершина помещена
             // -1, если процесс размещения не завершен
int order[N],norder; // порядок вершин и число помещенных
int topsortrec(int i)
{ 
  if(used[i]) return used[i]>0;
  used[i]=-1;
  for(int j=0; j<n; ++j)
    if(connect[j][i]) // если есть дуга j->i 
      if(!topsortrec(j)) // пытаемся поместить вершину j
        return 0;
  // все предшественники размещены
  order[norder++]=i; // кладем вершину i
  used[i]=1;
  return 1;
}
int topsort()
{
  norder=0;
  // помещаем все вершины в order
  for(int i=0; i<n; ++i)
  { if(!topsortrec(i)) 
      return 0;
  }
  return 1;
}