2015年7月26日星期日

Leetcode: Basic Calculator II

Initial codes:
Speed is high O(n)--n is size of string
Key: use lastnum to record the last number before current operator
         calc lastnum when number
         calc lastnum to sum when +-
         set opt when */
opt records the most recent operator
sign plays magic here. It records +/- before the current operator.  It also records +/- before */ which helps to add lastnum to get final result.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public:
    int calculate(string s) {
    //for loop
        //opt: 0=+-; 1=*; 2=/;
        //sign: 1=+ -1=-
        //when number:  get num
         //             if +- lastnum =num
         //             if */ lastnum =lastnum*/num
        //when +/-: add the number before  +/- (lastnum) to sum, set opt
        //when */: set opt
    //sum+=sign*lastnum
        int sign=1;
        int opt=0;
        int sum=0;
        int lastnum;
        for(int i = 0; i < s.size(); i++){
            if(s[i] >= '0' && s[i] <= '9'){
                int num = 0;
                while(i < s.size() && s[i] >= '0' && s[i] <= '9'){
                    num = num * 10 + s[i] - '0';
                    i++;
                }
                //i--;
                if(opt == 0) lastnum = num;
                if(opt == 1) lastnum *= num;
                if(opt == 2) lastnum /= num;
            }
            if(s[i] == '+') {
                sum += sign * lastnum;
                opt = 0;
                sign = 1;
            }
            if(s[i] == '-'){
                sum += sign * lastnum;
                opt = 0;
                sign = -1;
            }
            if(s[i] == '*'){
                opt = 1;
            }
            if(s[i] == '/'){
                opt = 2;
            }
        }
        sum += sign * lastnum;
        return sum;
    }
};

reference:
for initial codes:
http://www.wengweitao.com/leetcode-basic-calculator-ii.html




2015年7月18日星期六

LeetCode: Basic Calculator

Way 1: transition from (inorder expression / infix notation) to (RPN(reverse polish notation) / postfix notation)
Shunting-yard algorithm or operator-precedence parsing
Further discussed in Basic Calculator II

Way 2: O(n)
Below is a widely used JAVA example ( not written by me):
Running the test expression in mind is the best way to understand it.
e.g. 2-(5-6); 3-(2-(5-6)+3);
This solution uses a stack to store operators based on parentheses and calculates the result orderly.
In an expression, the operands are always one more than operator. So we need to push 1 twice into stack at the
beginning to make sure that there is at least one element stored in the bottom of stack for the next operator to
get stack.peek()

The Key is to realize that operators in parentheses is based on the status before the parentheses.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<Integer>();
        stack.push(1);
        stack.push(1);
        int res = 0;
        for(int i=0; i<s.length(); i++){
            char tmp = s.charAt(i);
            if(Character.isDigit(tmp)){
                int num = tmp - '0';
                int j = i+1;
                while(j<s.length() && Character.isDigit(s.charAt(j))){
                    num = num * 10 + s.charAt(j) - '0';
                    j++;
                }
                i = j-1;
                res += stack.pop() * num;
            }else if(tmp == '+' || tmp == '('){
                stack.push(stack.peek());
            }else if(tmp == '-'){
                stack.push(-1*stack.peek());
            }else if(tmp == ')'){
                stack.pop();
            }
        }
        return res;
    }
}

My codes(c++):


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int calculate(string s) {
        int res = 0;
        stack<bool> mystack;
        mystack.push(true);
        mystack.push(true);
        for(int i = 0; i < s.size(); i++){
            char c = s[i];
            if(c == '+' || c == '(') mystack.push(mystack.top());
            if(c == '-') mystack.push(!mystack.top());
            if(c == ')') mystack.pop();
            if(isdigit(c)){
                int num = c - '0';
                int j = i + 1;
                while(j < s.size() && isdigit(s[j])){
                    num = num * 10 + s[j] - '0';
                    j++;
                }
                i = --j;
                if(mystack.top()) res += num;
                else res -= num;
                mystack.pop();
            }
        }
        return res;
    }
};

Reference:
Wikipedia--RPN
explains the steps well
JAVA example








LeetCode: Container With Most Water

Initial version:
O(n*n)
compare area of all two points.
too time consuming and cannot pass test.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    int maxArea(vector<int>& height) {
        int area=0;
        for(int i = 0; i < height.size(); i++){
            for(int j = i + 1; j < height.size(); j++){
                int w = j - i;
                int h = (height[i] < height[j]) ? height[i] : height[j];
                int temparea = w * h;
                if(temparea > area) area = temparea;
            }
        }
        return area;
    }
};
Analysis:
This version can be optimized by recording the min height which has been iterated. If the current height is less than the recorded min height, all areas that stared with current height will less than the max area started with the recorded min height. So we don't need to calculate areas started with current height and just jump to the next element.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int area=0;
        int minh=height[0];
        for(int i = 0; i < height.size(); i++){
            if(height[i] < minh) continue;
            for(int j = i + 1; j < height.size(); j++){
                int w = j - i;
                int h = (height[i] < height[j]) ? height[i] : height[j];
                int temparea = w * h;
                if(temparea > area) area = temparea;
            }
        }
        return area;
    }
};
However, the time complexity is still O(n*n) in worst case.

Two-pointer scan:
O(n)
Area is only decided by the beginning and ending heights.
When the short side is fixed, the area reduces when the right side moves forward the short side. So we can keep the tall side and only move the short side. This makes sure that the largest area will be iterated.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0;
        int right = height.size() - 1;
        int maxArea = 0;
        while(left < right){
            int w = right - left;
            int h = (height[left] < height[right]) ? height[left] : height[right];
            int area = w * h;
            if(area > maxArea) maxArea = area;
            if(height[left] < height[right]) left++;
            else right--;
        }
        return maxArea;
    }
};



Reference:
http://yucoding.blogspot.com/2012/12/leetcode-question-22-container-with.html

2015年7月17日星期五

LeetCode: Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Initial codes:
check each element to get the length that sums to s.
Time complexity O(n*n) Space complexity O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int minLen = 0;
        for(int i = 0; i < nums.size(); i++){
            int len = 0;
            int sum = 0;
            int j = i;
            while(sum < s){
                if(j >= nums.size()) return minLen;
                sum += nums[j];
                len++;
                j++;
            }
            if(i == 0) minLen = len;
            else if(len < minLen) minLen = len;
        }
        return minLen;
    }
};

Sliding window
Set left and right. if sum > s, left++; if sum < s, right++;
O(n)  O(1)
Note:
1)The key is is the terminal condition of while loop.
if(sum < s){}  should run when right<nums.size()
else{} should run when right<nums.size()+1 ==> make sure that the left is able to move when right==nums.size(), right is larger by 1 than current real right.
2) Line 15 will compare current distance to previous distance. We can initiate distance to any value bigger than nums.size(). INT_MAX is also a great idea.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0;
        int right = 0;
        int sum = 0;
        int dist = nums.size()+1;
        while(1){
            if(sum < s) {
                if(right >= nums.size()) break;
                sum += nums[right];
                right++;
            }
            else {
                if(right - left < dist) dist = right - left;
                sum -= nums[left];
                left++;
            }
        }
        if(dist == nums.size() + 1) return 0;
        return dist;
    }
};

Here the right and left are bigger than the left and right of dist, which makes logics kind of messy.
If we put right++ before calculating sum, logics are easier to understand.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int left = 0;
        int right = 0;
        if(!nums.size()) return 0;
        int sum = nums[0];
        int dist = nums.size()+1;
        while(right < nums.size()){
            if(sum < s){
                right++;
                if(right >= nums.size()) continue;
                sum += nums[right];
            }
            else{
                if(right - left + 1 < dist) dist = right - left + 1;
                sum -= nums[left++];
            }
        }
        if(dist == nums.size() + 1) return 0;
        return dist;
    }
};

This version is easy to understand. However, Line 12 is necessary to make sure the index is within the vector range. Even though this code can pass leetcode test without line 12.

Binary search: O(nlogn)
Frame of binary search:
1
2
3
4
5
6
7
8
9
int bs(int val[], s){
    int left, right;
    while(left <= right){
          int mid = (left + right) / 2;
          if(val[mid] < s) left = mid + 1;
          else right = mid - 1;
    }
  return left;
} 

s1: create a sums array, the size is 1 larger than nums array. 
      sums[i] means sum from nums[0] to nums[i-1]
      sums[n] - sums[i] means sum from nums[i] to nums[n-1]

      if the size equals to nums array, we are unable to represent sums starts 0 by sums[n]-sums[0] format.
In this case:
      sums[i] means sum from nums[0] to nums[i]
      sums[n] - sums[i] means sum from nums[i+1] to nums[n]
      Then we've to discuss sum starts from nums[0] separately.

s2: Iterate the sum array to get the minimum size subarray starts with each element.
      In each iteration, using binary search to look for the first element that makes sub sum larger or equal to s. We can get the minimum length with this index. This is my way.
      Actually, this way is not concise enough. Because we have to differentiate the final value is larger than s or just the while loop ends. It is possible that indexes from left to right are all not the answer, which is not satisfy an binary search assumption that there must be a answer between left and right.
     However, we can make things simple if we just return the index left. The while loop always stops when the left is 1 larger than right. If right = mid - 1 (Line 30) never run, left will be larger than the initial right. In other cases, the final left value is the minimum index that makes sum from start to left be more or equal to s. I didn't realize this way. Reference to http://www.cnblogs.com/grandyang/p/4501934.html

Note: Remember framework of binary search
   

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        //creating sum array
        //iterate each element to get the the shortest length with binary search
        vector<int> sums(nums.size()+1);
        sums[0] = 0;
        for(int i = 0; i < nums.size(); i++){
            sums[i+1] = sums[i] + nums[i];
        }
        int minLen = INT_MAX;
        for(int i = 0; i < nums.size(); i++){
            int curLen = getLen(sums, i, s);
            if(curLen == 0) continue;
            if(curLen < minLen) minLen = curLen;
        }
        if(minLen == INT_MAX) return 0;
        return minLen;
    }
    int getLen(vector<int>& sums, int start, int s){
        int left = start;
        int right = sums.size() - 1;
        int len = 0;
        while(left <= right){
            int mid = (left + right) / 2;
            if(sums[mid] - sums[start] < s){
                left = mid + 1;
            }else{
                len = mid -start;
                right = mid - 1;
            }
        }
        return left;
    }
};




Reference:
sliding window method
sliding window with three while loops
binary search method
Giving process of binary search solution

2015年7月16日星期四

LeetCode: Find Peak Element

Initial codes:
Use three pointers to track three adjacent numbers.
Note: write sudo codes for logics first.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left, cur, right;
        left = -1;
        cur=0;
        right=1;
        //for(int cur=0; cur<nums.size(); cur++){
        while(cur<nums.size()){
            // if cur < left l, c, r ++
            if(left < 0 || nums[left] > nums[cur]){
                left++;
                cur++;
                right++;
                continue;
            }
            // if cur > left, if cur > right, return cur
            //                if cur < right, l, c, r ++     
            if(right >= nums.size() || nums[cur] > nums[right]) return cur;
            else{
                left++;
                cur++;
                right++;
            }
        }
        
    }
};

Analysis:
worst case: complexity O(n)
The codes can be simplified to just find the first element which is smaller than its adjacent front element.

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        for(int i=1; i<nums.size(); i++){
            if(nums[i-1] > nums[i]) return i-1;
        }
        return nums.size()-1;
    }
};

Optimization: binary search
 O(log n)
Recursive:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int bs(int left, int right, vector<int>& nums){
        if(left == right) return left;
        int mid = (left + right) / 2;
        if( nums[mid] > nums[mid + 1]) return bs(left, mid, nums);
        if( nums[mid] < nums[mid + 1])  return bs(mid+1, right, nums);
    }
    int findPeakElement(vector<int>& nums) {
        return bs(0, nums.size()-1, nums);
    }
};
While loop:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        while(left <= right){
            if(left == right) return left;
            int mid = (left + right)/2;
            if( nums[mid] > nums[mid + 1]) {
                right = mid;
            }else{
                left = mid + 1;
            }
        }
    }
};


Reference:
http://blog.csdn.net/u010367506/article/details/41943309



2015年7月13日星期一

LeetCode: Implement Trie(Prefix Tree)


Tries:
For TrieNode(), array is used to store next nodes address.



insert(): jump to the next node according to char of string.
NOTE: If I want to get the the address of a pointer,  I have to use pointers to pointers.(二级指针)
<way 1>  judge the next node is null or not, if null, create a new one.
<way 2>  judge the current pointer is null or not, if null, create a new one. (use pointers to pointers here, since we need to store the address of the current pointer to create a new node. If we store the current pointer directly when the current pointer is null, then we will lost the address to create a new node). This way is too complex and not necessary, and I write it for fun.
Cannot use & reference here, since the nature of reference is a constant pointer to pointer. That's why reference has to be initialized when created.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void insert(string word) {
        TrieNode** curNode = &root;
        for(int i=0; i < word.size(); i++){
            int pos = word[i]-'a';
            if(*curNode == NULL) *curNode = new TrieNode();
            curNode = &((*curNode)->children[pos]);
        }
        if(*curNode == NULL) {
   *curNode = new TrieNode();
        }
        if((*curNode)->val == false) {
   (*curNode)->val = true;
        }
    }

search(): similar to insert except when the node is null, return false.

startsWith(string prefix): similar to search for prefix. If all nodes for prefix exist, then we need to traverse all sub nodes after prefix. I used BFS to traverse the end of prefix and all sub nodes to make sure at lease one sub node has value of true.
Here, if only prefix exist is ok. e.g. insert("a") starsWith("a") should return true.

~Trie()  delete itself recursively


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
class TrieNode {
public:
    // Initialize your data structure here.
    bool val;
    TrieNode* children[26];
    TrieNode() {
        val=false;
        for(int i=0; i<26; i++){
            children[i]=NULL;
        }
    }
    void Delete(){
        for(int i = 0; i < 26; i++){
            if(children[i] != NULL) children[i]->Delete();
        }
        delete this;
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }
    ~Trie(){
        if(root != NULL) root->Delete();
    }
    // Inserts a word into the trie.
   void insert(string word) {
        TrieNode* curNode = root;
        for(int i = 0; i < word.size(); i++){
            int pos = word[i]-'a';
            if(curNode->children[pos] == NULL) curNode->children[pos] = new TrieNode();
            curNode = curNode->children[pos];
        }
        if(curNode->val == false) curNode->val = true;
    }
    
    // Returns if the word is in the trie.
    bool search(string word) {
        TrieNode* curNode = root;
        for(int i = 0; i < word.size(); i++){
            int pos=word[i]-'a';
            if(curNode == NULL) {
    return false;
      }
            curNode = curNode->children[pos];
        }
        if(curNode == NULL) {
   return false;   
        }
        return curNode->val;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    bool startsWith(string prefix) {
        TrieNode* curNode = root;
        for(int i = 0; i < prefix.size(); i++){
            int pos = prefix[i] - 'a';
            if(curNode == NULL) return false;
            curNode = curNode->children[pos];
        }
        if(curNode == NULL) return false;
        queue<TrieNode*> q;
        q.push(curNode);
        while(!q.empty()){
            TrieNode* cur = q.front();
            q.pop();
            if(cur->val == true) return true;
            for(int i = 0; i < 26; i++){
                if(cur->children[i] != NULL) q.push(cur->children[i]);
            }
        }
        return false;
    }

private:
    TrieNode* root;
};



Analysis:
Speed is just at the average level. Optimization is needed.
(1) startswith():
For a trie without deletion operation, we only need to traverse nodes corresponding string prefix regardless of val. So I rewrite this function. It is almost same with search() without judgement of value.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
bool startsWith(string prefix){
         TrieNode* curNode = root;
         int len = prefix.size();
         for(int i=0; i<len; i++){
             int pos=prefix[i]-'a';
             if(!curNode->children[pos]) return false;
             curNode = curNode->children[pos];
         }
         return true;
     }
(2) the destructor I wrote also take a long time. After deletion. speed is much better.


Reference:
百科pointers to pointers
How to get address from an array
Interesting understand of &
destructor for Trie
Yu's garden for optimization

2015年7月10日星期五

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...
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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