leetcode Question: Course Schedule

Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]

There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

Analysis:

This is a classic Graph topology sorting problem, but an easy version. We don't have to store the sort, in other words, we only need to detect if exists cycle in a directed graph.

Both DFS and BFS can be used to solve this problem.

First of all, we need to get a representation of the graph, either adjacency matrix or adjacency list is OK. In my code, you can see both ways. But note that, when the number of vertex is large, adjacency matrix usually is NOT a good option.

In DFS, the general idea, is to search each vertex in the graph recursively, if the current vertex has been visited in this search, then there must be a cycle. Be careful with the status of each vertex, here in my code, it has three states:  unvisited (=0), visited(=1), searching(=-1). The third states is to detect the existence of cycle, while the 2nd state indicate that the vertex is already checked and there is no cycle.

In BFS, the idea is much easier.  We store the indegree of each vertex, push the vertices with 0 indegree in stack (remember general BFS framwork?).  Every time, pop the stack and set indegree of connected vertices -1. In the end, if the number of popped out vertices is less than the total number of vertices in the original graph, there is cycle.


Note, in the test cases, there exist duplicates in prerequisites array.
    

BFS
Code(C++):

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> ind(numCourses,0); //indegree vector
        
        //construct map & get indegree of each vertex
        vector<vector<bool> > map(numCourses, vector<bool>(numCourses, false));
        for (int i=0;i<plen;i++){
            //Important: in case of duplicates in prerequisites, only +1 indegree 
            if (map[prerequisites[i].first][prerequisites[i].second] == false){
                map[prerequisites[i].first][prerequisites[i].second] = true;
                ind[prerequisites[i].first]++;
            }
        }
        
        //BFS
        stack<int> st;
        for (int i=0;i<numCourses;i++){
            if (ind[i]==0) st.push(i);
        }
        
        int count = 0;  // to get the bool result
        
        while (!st.empty()){
            int tmp = st.top();
            st.pop();
            count ++;
            for (int i=0;i<numCourses;i++){
                if (map[i][tmp]){
                    ind[i]--;
                    if (ind[i]==0) st.push(i);
                }
            }
        }
        return count < numCourses ? false : true;
        
    }
};

Code(Python):

class Solution:
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        map = [[] for x in range(numCourses)]
        ind = [0 for x in range(numCourses)]
        
        for p in prerequisites:
            if p[0] not in map[p[1]]:
                ind[p[0]] += 1
                map[p[1]].append(p[0])
        st = []
        for i in range(numCourses):
            if ind[i] == 0:
                st.append(i)
        count = 0
        while st:
            tmp = st[0]
            st.pop(0)
            count += 1
            for i in map[tmp]:
                ind[i] -= 1
                if ind[i] == 0:
                    st.append(i)
                        
        if count < numCourses:
            return False
        else: 
            return True
        
        

DFS
Code(C++):

class Solution {
public:
    bool dfs(int v, vector<int> &visit, vector<set<int> > &gr){
        if (visit[v] == 1){return true;}
        visit[v] = -1;
        for (auto it = gr[v].begin(); it != gr[v].end(); it++){
            if (visit[*it] == -1 || ! dfs(*it, visit, gr)){
                return false;
            }
        }
        visit[v] = 1;
        return true;
    }
    
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        int plen = prerequisites.size();
        vector<int> visit(numCourses,0);
        vector<set<int> > gr(numCourses);
        
        for (int i=0;i<plen;i++){
            gr[prerequisites[i].second].insert(prerequisites[i].first);
        }
        
        for (int i=0;i<numCourses;i++){
            if (!dfs(i, visit, gr)) return false;
        }
        return true;
    }
};

Code(Python):

class Solution:
    def dfs(self, v, visit, gr):
        if visit[v] == 1:
            return True
        visit[v] = -1;
        for i in gr[v]:
            if visit[i] == -1 or not self.dfs(i, visit, gr):
                return False
        visit[v] = 1
        return True
    
    # @param {integer} numCourses
    # @param {integer[][]} prerequisites
    # @return {boolean}
    def canFinish(self, numCourses, prerequisites):
        gr = [[] for x in range(numCourses)]
        visit = [0 for x in range(numCourses)]
        
        for p in prerequisites:
            if p[0] not in gr[p[1]]:
                gr[p[1]].append(p[0])
                
        for v in range(numCourses):
            if visit[v]!=1:
                if not self.dfs(v, visit, gr):
                    return False
        return True

leetcode Question: Clone Graph

Clone Graph

     Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

OJ's undirected graph serialization:

Nodes are labeled uniquely.

We use # as a separator for each node, and , as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph {0,1,2#1,2#2,2}.

The graph has a total of three nodes, and therefore contains three parts as separated by #.

1. First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
2. Second node is labeled as 1. Connect node 1 to node 2.
3. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

       1
      / \
     /   \
    0 --- 2
         / \
         \_/

Analysis:

At the first look, this problem seems wired. Remind the Copy Constructor of a class object, when the class member contains pointers, the direct copy is shadow, we need deep copy. For this problem, there are two major tasks:
(1)  Traverse the graph
(2)  Construct the new graph at the same time.

Traverse the graph is similar to the tree traversal, both DFS and  BFS can be used. Slight difference  is to consider the loop in the graph (e.g., the 2-->2 in the above figure), thus we need store the visited vertex information. If the neighbor of current node has not been visited, then search that node.

Only one point should be noticed for constructing the new graph, in the code below, I used a map< int, node*> to store the visited information, so that if the node has been visited, just add the map[int] to the current node's neighbor list. Be careful the current node is the node you "newed", but not the node in the original graph (line 12 and 13 in the code below. If you set visited[v->label] = v, it is not correct.).

Code:

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
public:
    UndirectedGraphNode* dfs(UndirectedGraphNode *v, map<int, UndirectedGraphNode*> &visited){
        UndirectedGraphNode* res = new UndirectedGraphNode(v->label);
        visited[v->label]=res;
        for (int i=0;i<v->neighbors.size();i++){
            if (!visited[v->neighbors[i]->label]){
                res->neighbors.push_back(dfs(v->neighbors[i],visited));
            }else{
                res->neighbors.push_back(visited[v->neighbors[i]->label]);
            }
        }
        return res;
    }
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (node==NULL){
            return NULL;
        }else{
            map<int, UndirectedGraphNode*> visited;
            UndirectedGraphNode* res = dfs(node, visited);
            return res;
        }
           
    }
};