gistfile1.ec

void TopoSort(LinkList<External, link = link> input)
{
   LinkList<External, link = link> L { };
   LinkList<External, link = link> S { };
   External n, next;

   for(n = input.first; n; n = next)
   {
      next = n.link.next;
      if(!n.incoming.count)
      {
         input.Remove((IteratorPointer)n);
         S.Add(n);
      }
   }

   while(true)
   {
      TopoEdge e, ne;
      if((n = S.first))
      {
         S.Remove((IteratorPointer)n);
         L.Add(n);
         for(e = n.outgoing.first; e; e = ne)
         {
            External m = e.to;
            ne = e.out.next;

            n.outgoing.Remove((IteratorPointer)e);
            m.incoming.Remove((IteratorPointer)e);
            delete e;

            if(!m.incoming.count)
            {
               input.Remove((IteratorPointer)m);
               S.Add(m);
            }
         }
      }
      else
      {
         if(input.count)
            PrintLn("Error: Graph has cycles!");
         else
         {
            input.first = L.first;
            input.last = L.last;
            input.count = L.count;
            L.first = null;
            L.last = null;
            L.count = 0;
         }
         break;
      }
   }

   delete L;
   delete S;
}