# Topological sort using STL

I am trying to implement topological sort using STL. I have used vector of lists to store adjacency list. Indegree is an array which stores indegree of vertices.

Indegree0 is a queue implemented using STL list to store vertices with indegree 0. Can someone please help me improve my code?

# include <iostream>
# include <bits/stdc++.h>
using namespace std;

vector<int> topologicalsort(vector<list<int> > adjacencylist,int  indegree[],int v,int e)
{

vector<int>ans(v+1);
int k=1;
//list to store vertices with indegree 0
list<int>indegree0;
for(int i=1;i<=v;i++)
{
if(indegree[i]==0)
indegree0.push_back(i);
}
while(!indegree0.empty())
{
int x=indegree0.front();
indegree0.pop_front();
ans[k]=x;
k++;
{
indegree[*itr]--;
if(indegree[*itr]==0)
indegree0.push_back(*itr);
itr++;
}
}
return ans;
}

int main()
{
int v,e;
cin>>v>>e;
int indegree[v+1];
for(int i=1;i<=v;i++)
indegree[i]=0;
for(int i=1;i<=e;i++)
{
int v1,v2;
cin>>v1>>v2;
indegree[v2]++;
}
for(int i=1;i<=v;i++)
{
{
cout<<*itr<<"  ";
itr++;
}
cout<<endl;
}
for(int i=1;i<=v;i++)
cout<<ans[i]<<"  ";

}

• Seems to require an input stream on stdin - can you provide a sample input? – Toby Speight Aug 31 '17 at 17:16

#include "bits/stdc++.h"


That's not a standard C++ header; prefer to use standard headers so that others can use your code.

using namespace std;


Bringing all names in from a namespace is problematic; namespace std particularly so. See Why is “using namespace std” considered bad practice?.

Used but not included: <cstdio>, <vector>, <list>. I'd recommend you stick to one of <cstdio> and <iostream>.

# Function signature

std::vector<int> topologicalsort(std::vector<std::list<int> > adjacencylist,
int indegree[], int v,
int e)


Why do you require e? It's never used.

Passing indegree as a pointer and length is very C-style; prefer a C++ range (e.g. a pair of iterators, or a standard container).

There's no need to pass adjacencylist by value: a const-ref is more appropriate.

# Result vector

Instead of creating v+1 elements in the result vector and having to keep track of our insert position with k, we can create it empty and push_back each result as we find it. We can avoid reallocation by using reserve().

# Looping over elements

Instead of the error prone iterator-based loop, prefer to use range-based for when applicable:

    for (int i: adjacencylist[x]) {
if (--indegree[i] == 0)
indegree0.push_back(i);
}


# Variable-length arrays

This is a non-standard extension:

int indegree[v+1];


It's not clear why you ignore the 0th element of these arrays; that probably warrants a comment.

# Cleaned code

#include <iostream>
#include <list>
#include <vector>

std::vector<int> indegree)
{
std::vector<int> ans;
ans.reserve(indegree.size()+1);
//list to store vertices with indegree 0
std::list<int> indegree0;
for (size_t i = 1;  i < indegree.size();  i++) {
if (indegree[i] == 0)
indegree0.push_back(i);
}
while (!indegree0.empty()) {
const int x = indegree0.front();
indegree0.pop_front();
ans.push_back(x);
for (const int i: adjacencylist[x]) {
if (--indegree[i] == 0)
indegree0.push_back(i);
}
}
return ans;
}

int main()
{
int v, e;
std::cin >> v >> e;
std::vector<int> indegree(v+1);
for (int i = 1;  i <= e;  i++) {
int v1, v2;
std::cin >> v1 >> v2;
++indegree[v2];
}
for (int i = 1;  i <= v;  i++) {
std::cout << "adjacencylist[" << i << "%d] :";
std::cout << j << "  ";
}
std::cout << std::endl;
}
auto const& ans = topologicalsort(adjacencylist, std::move(indegree));
for (int i: ans)
std::cout << i << "  ";
}


1. To make your intent clearer, use std::queue when you need queue. Don't reinvent the wheel. Don't confuse those who read your code.

2. Iteration over std::list is very inefficient because it lacks memory locality. Don't use it unless you have a very good reason to. Use std::vector as a default container.

3. Separate the words in variable's names somehow (either using camelCase or underscores). topologicalsort looks sort of gibberish. topological_sort or topologicalSort looks better, doesn't it?

4. Even if the input and output should have 1-based indexing, I'd still use 0-based indexing in computations. It's more conventional so it makes your code easier to understand (That's the main reason. Saving one element isn't a big deal).

Why does the function topological_sort take more than one parameter? It should be able to calculate indegree0 by itself.
Why is it restricted to int instead of allowing any type?