# My Wiki topological sort C++ implementation without adjacency list conversion

• My code based on Wiki topological sort. It is still slow but passed OJ:

``````bool hasNoIncomingEdge(int n, vector<pair<int, int>>& prerequisites) {
for (int j=0; j<prerequisites.size(); j++) {
if (n == prerequisites[j].first)
return false;
}
return true;
}
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) { // 432 ms, BFS(Topological Sort)
//L ← Empty list that will contain the topologically sorted elements
queue<int> Q; // set of all nodes with no incoming edges
for (int i=0; i<numCourses; i++) { // collect all nodes with no incoming edges
if (hasNoIncomingEdge(i, prerequisites))
Q.push(i);
}
while(!Q.empty()) {
int n = Q.front(); Q.pop();
// add n to tail of L
for (int j=prerequisites.size()-1; j>=0; j--) {
if (n == prerequisites[j].second) {
int m = prerequisites[j].first;
prerequisites.erase(prerequisites.begin()+j);
if (hasNoIncomingEdge(m, prerequisites))
Q.push(m);
}
}
}
return prerequisites.empty(); // not empty means still has edge at least one cycle
}
``````

Here is the DFS part passed OJ after fixed the initial TLE error. It is much slower than adjacency list based solution.

``````//https://en.wikipedia.org/wiki/Topological_sorting
bool dfs_pair(int n, int numCourses, vector<bool>& tempMark, vector<bool>& permMark, vector<pair<int, int>>& prerequisites) { // 380 ms
if (tempMark[n] == true) return false; //visited along the path, stop, cycle found, not a DAG
tempMark[n] = true; // mark n temporarily
for (int j=prerequisites.size()-1; j>=0; j--) { // for each node m with an edge from n to m
if (prerequisites[j].second==n) {
int m = prerequisites[j].first;
prerequisites.erase(prerequisites.begin()+j);
if (!dfs_pair(m, numCourses, tempMark, permMark, prerequisites)) // visit m
return false;
}
}
permMark[n] = true; // mark n permanently
tempMark[n] = false; // unmark n temporarily
//add n to head of L
return true;
}
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
// L <- Empty list that will contain the sorted nodes
vector<bool> tempMark(numCourses), permMark(numCourses);
for (int i=0; i<numCourses; i++) {
if (permMark[i] == false)
if (!dfs_pair(i, numCourses, tempMark, permMark, prerequisites))
return false;
}
return true;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.