I'm trying to solve a topological sort problem on Leetcode(link here). And I was surprised to find that C++ is slower than Java with same algorithm! C++ solution costs almost 500ms, but Java is only 6~7ms. It's confusing... And C++ is also slower than python, c# and javascript. Here is the accepted solutions runtime distribution:
And here is the code for C++ version and Java version. Both of them use DSF method for topological sort.
//Java
public int[] findOrder(int numCourses, int[][] prerequisites) {
List<Integer>[] edges = new ArrayList[numCourses];
int[] visited = new int[numCourses];
int[] res = new int[numCourses];
for (int i = 0; i < edges.length; i++)
edges[i] = new ArrayList<Integer>();
for (int[] edge : prerequisites)
edges[edge[0]].add(edge[1]);
for (int i = 0, j = 0; i < numCourses; i++) {
j = dfs(i, edges, visited, res, j);
if (j == -1) return new int[0]; // cycle, return empty array
}
return res;
}
private int dfs(int v, List<Integer>[] edges, int[] visited, int[] res, int i) {
if (visited[v] == 2) return i; // black node
if (visited[v] == 1) return -1; // gray node -> cycle
visited[v] = 1;
for(int j : edges[v]) {
i = dfs(j, edges, visited, res, i);
if (i == -1) return -1; // if there is a cycle, propagate the error
}
visited[v] = 2;
res[i] = v;
return i+1;
}
--
//C++
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
vector<int> outputs;
vector<int> nodes(numCourses, 0);
vector<list<int>> edges(numCourses);
for (auto i=prerequisites.begin(); i!=prerequisites.end(); i++) {
edges[i->first].push_back(i->second);
}
for(int i=0; i<numCourses; ++i)
{
if(!dfs(edges, outputs, nodes, i, numCourses))
{
outputs.clear();
return outputs;
}
}
return outputs;
}
bool dfs(vector<list<int>>& edges, vector<int>& outputs, vector<int>& nodes, int cur, int numCourses)
{
if(nodes[cur] == 1) return false;
if(nodes[cur] == 0)
{
nodes[cur]++;
for(auto i=edges[cur].begin(); i!=edges[cur].end(); ++i)
{
if(!dfs(edges, outputs, nodes, *i, numCourses))
return false;
}
nodes[cur]++;
outputs.push_back(cur);
}
return true;
}
