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


  • 0
    H

    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;
    }

Log in to reply
 

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