title: A C++ implementation of topological ordering
body: <p>This morning I was doing my C++ class assignment, an implementation of topological ordering. There's no error while compiling, but simply can't run. Since I'm not quite familiar with pointers or STL, nor the VS debugger...I just can't figure out where went wrong. It would help me a lot if someone can point out my errors. Tons of thanks!</p>
  
  <p>Here's my code:</p>
  
  <pre><code>#include&lt;iostream&gt;
  #include&lt;vector&gt;
  #include&lt;queue&gt;
  
  using namespace std;
  
  typedef struct Vertex{
      int index;
      int indegree;  // indegree of vertex v is the total num of edges like(u,v)
      vector&lt;Vertex&gt;adjacent;
      int topoNum;    // topological order of this vertex.
  }Vertex;
  typedef struct Edge{
      Vertex start;
      Vertex in;
  }Edge;
  
  Vertex*InDegrees(int numVertex,int numEdge,Edge*edges) // calculate indegrees of all vertices.
  {
      Vertex*vertices=new Vertex[numVertex];
      for(int i=0;i&lt;numVertex;i++){   vertices[i].index=i;    vertices[i].indegree=0;}
      for(int i=0;i&lt;numEdge;i++)
      {
          int j=edges[i].in.index;
          vertices[j].indegree++;
          vertices[j].adjacent.push_back(edges[i].start);
      }
      return vertices;
  }
  
  int*topoSort(int numVertex,int numEdge,Edge*edges)
  {
      edges=new Edge[numEdge];
      Vertex*Vertices=new Vertex[numVertex];
      Vertices=InDegrees(numVertex,numEdge,edges);
  
      queue&lt;Vertex&gt;q;
      for(int i=0;i&lt;numVertex;i++)
      {
          if(Vertices[i].indegree==0)
              q.push(Vertices[i]);
      }
  
      int count=0;
      while(!q.empty())   // Ordering completed when queue is empty.
      {
          Vertex v=q.front();    // get the vertex whose indegree==0
          q.pop();
          v.topoNum=++count;
          vector&lt;Vertex&gt;::iterator iter;
          for(iter=v.adjacent.begin();iter!=v.adjacent.end();iter++)
          {
              Vertex w=*iter;
              if(--w.indegree==0)
                  q.push(w);
          }
      }
      int*topoOrder=new int[numVertex];
      for(int i=0;i&lt;numVertex;i++)
      {
          int j=Vertices[i].topoNum;
          topoOrder[j]=-1;    // initial value, in case cycle existed.
          topoOrder[j]=Vertices[i].index;
      }
      delete[]Vertices;
      delete[]edges;
      return topoOrder;
  }
  
  int main()
  {
      int numVertex,numEdge;
      cin&gt;&gt;numVertex&gt;&gt;numEdge;
      Edge*Edges=new Edge[numEdge];
      int indexStart,indexIn;
      for(int i=0;i&lt;numEdge;i++)
      {
          cin&gt;&gt;indexStart&gt;&gt;indexIn;
          Edges[i].in.index=--indexIn;
          Edges[i].start.index=--indexStart;
      }
  
      int*topoOrder=new int[numVertex];
      topoOrder=topoSort(numVertex,numEdge,Edges);
      for(int i=0;i&lt;numVertex-1;i++)
      {
          if(topoOrder[i]==-1)
          {
              cout&lt;&lt;"Cycle exists, not a DAG!";
              return 0;
          }
          cout&lt;&lt;topoOrder[i]&lt;&lt;",";
      }
      cout&lt;&lt;topoOrder[numVertex-1]&lt;&lt;endl;
  
      delete[]Edges;
      return 0;
  }
  </code></pre>