NO CODING NO LIFE: LeetCode: Course Schedule

As the hints, this problem is to find if a cycle exists in a directed graph.
Solution: Topological sort via DFS and BFS

Topological sort via DFS:

The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node): (from WIKI)
Specifically, when the algorithm adds node n, we are guaranteed that all nodes which depend on n are already in the output list L:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

Initial ugly code with slow speed...

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        unordered_set<int> sortedList; 
        unordered_set<int> tempList;
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, prerequisites, sortedList, tempList)) return false;
        }
        return true;
    }
    bool visit(int n, vector<pair<int, int>>& prerequisites, unordered_set<int>& sortedList, unordered_set<int>& tempList){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(int i=0; i<prerequisites.size(); i++){
            if(prerequisites[i].first == n) {
                if( !visit(prerequisites[i].second, prerequisites, sortedList, tempList) ) return false;
            }
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

After putting sortedList and tempList in Line 4 and 5 above as a member of Solution, speed increases, but still not a good one.

class Solution {
public:
    unordered_set<int> sortedList; 
    unordered_set<int> tempList;
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //unordered_set<int> sortedList; 
        //unordered_set<int> tempList;
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, prerequisites)) return false;
        }
        return true;
    }
    bool visit(int n, vector<pair<int, int>>& prerequisites){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(int i=0; i<prerequisites.size(); i++){
            if(prerequisites[i].first == n) {
                if( !visit(prerequisites[i].second, prerequisites) ) return false;
            }
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

Analysis:
This method visit each vertices, and visit() cost O(E)(Line 18) to visit adjacent nodes.
So the whole time complexity is O(v*E)
Defects: took too much time to search adjacent node.
How to overcome: Change graph representation from edge lists to adjacency matrices or adjacency lists. It will take O(E) to establish the new lists and O(v) for all node to look for adjacent nodes.
Then time complexity is O(E)+O(V)

Optimized codes:

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector< set<int> > adjLists(numCourses);
        unordered_set<int> sortedList; 
        unordered_set<int> tempList;
        //establish adjLists
        for(int i=0; i<prerequisites.size(); i++){
            adjLists[prerequisites[i].first].insert(prerequisites[i].second);
        }
        //traverse vertices
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, adjLists, sortedList, tempList)) return false;
        }
        return true;
    }
    bool visit(int n, vector<set<int>>& adjLists, unordered_set<int>& sortedList, unordered_set<int>& tempList){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(auto it=adjLists[n].begin(); it != adjLists[n].end(); ++it){
            if(!visit(*it, adjLists, sortedList, tempList)) return false;
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

Topological sort via BFS:
First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

I use two sets to store edges.
IOLists stores all adjacent nodes that comes out from current index of vector
---- used to look for adjacent nodes for nodes in zeroInLists. (Line 19)
OILists stores all adjacent nodes that will come to the current index of vector
---- used to check the current node has no other incoming edges. (Line 23)

A normal BFS solution is to use array to record in-degree. Try later.

Note: 1. write sudo code before coding
2. give a good name, IOlist will be better than IOList, which adds many mistakes

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<set<int>> IOLists(numCourses);
        vector<set<int>> OILists(numCourses);
        for(int i=0; i<prerequisites.size(); i++){
            IOLists[prerequisites[i].first].insert(prerequisites[i].second);
            OILists[prerequisites[i].second].insert(prerequisites[i].first);
        }
        queue<int> zeroInLists;
        for(int i=0; i<OILists.size(); i++){
            if(OILists[i].empty()) zeroInLists.push(i);
        }
        while(!zeroInLists.empty()){
            //remove one element
            int cur=zeroInLists.front();
            zeroInLists.pop();
            //get all adjacent nodes
            for(set<int>::iterator it=IOLists[cur].begin(); it!=IOLists[cur].end();++it){
            //for each node, remove the edge
                OILists[*it].erase(cur);
                //if this node don't have input, add to zeroInlists
                if(OILists[*it].empty()) zeroInLists.push(*it);
            }
            IOLists[cur].clear();
        }
        //if both IOLists and OILists are empty return true, else false
        for(int i=0; i<numCourses; i++){
            if(!IOLists[i].empty() || !OILists[i].empty()) return false;
        }
        return true;
    }
};

Reference:
About graph concepts:
in-degree, out-degree
graph representation

About this problem:
use the second sudo code for dfs
https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
Use Yu's code to optimize:
http://yucoding.blogspot.com/2015/06/leetcode-question-course-schedule.html
Great explanation
http://www.cnblogs.com/grandyang/p/4484571.html

NO CODING NO LIFE

2015年7月10日星期五

LeetCode: Course Schedule

没有评论:

发表评论