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.

解题思路：

这道题可以转换成判断一个有向图是否有环，若有环，则不能完成，否则能完成。现将课程表示成一个有向图，用邻接表来存储。然后通过DSF来遍历图，若存在一个节点被访问了两次，则表明有环。

注意到这个图可能不是全连通图，所以，需要将每个节点作为开始节点来验证。为了减少遍历次数，用数组mark来记录以某个节点起始的节点进行深度遍历是否有环。下面是代码：

class Solution {
public:
    bool canFinish(int numCourses, vector>& prerequisites) {
        int len=prerequisites.size();
        if(len==0){
            return true;
        }
        vector> graph(numCourses, vector());   //邻接表表示的图
        for(int i=0; i>& graph, bool* visit, bool* mark, int current){
        if(visit[current]){
            return true;
        }
        if(mark[current]){
            return false;
        }
        visit[current] = true;      //标记已经访问过
        
        for(int i=0; i

 
转载请注明： » [LeetCode] Course Schedule

<!--
                    

                    	

                        	

                            	
                            
                        
                        

                        	

                            	
相关博文：
                                

                                	
                                    	
                                        	
                                        
                                        
定制桌面成功案例
                                    
                                    
                                    	
                                        	
                                        
                                        
海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）
                                    
                                    
                                    	
                                        	
                                        
                                        
汉字转拼音c/c++源码，支持gb2312和utf8
                                    
                                    
                                    	
                                        	
                                        
                                        
数据库顶级会议——SIGMOD介绍
                                    
                                
                            
                        
                    
                    -->