题目：leetcode

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.

分析：

本题目可转化为 “判断有向图中是否有环”。

1、把数组prerequisites中的内容放进哈希表table，table的key是课程编号，value是一个数组，记录了key代表的课程的约束条件（即上完value中的课程，才能上key的课程）。如果每一门课程当成平面上的一个点，那么key和value中的每一门课程，可以分别连成一条有向路径。

2、利用回溯法，如果没有环，则把相应的“路径”删除，直到把有向图删光。若有环，则整个程序返回false。

?

?

class Solution {
public:
    bool canFinish(int numCourses, vector
  
   >& prerequisites) {
        if(prerequisites.size()<=1)
            return true;
        
        unordered_map
   
    > table; for(auto &i:prerequisites) { table[i[0]].push_back(i[1]); } vector
    
      path; while(!table.empty()) { auto it=table.begin(); path.push_back(it->first); if(HasLoop(table,it->first,path)) return false; path.pop_back(); } return true; } //判断是否有环，有环
     的话返回真，否则返回假 bool HasLoop( unordered_map
     
      > &table,const int &begin,vector
      
        &path) { if(table.count(begin)==0) return false; while(!table[begin].empty()) { int temp=table[begin].back(); if(find(path.begin(),path.end(),temp)!=path.end()) return true; path.push_back(temp); if(HasLoop(table,temp,path)) return true; path.pop_back(); table[begin].pop_back(); } table.erase(begin); return false; } };
      
     
    
   
  

?