1选课问题
Leetcode上有这样一道题：有代号0，1，2……n-1的n门课程。其中选择某些课程需要另一些课程作为前提条件。用一组pair来表示这些条件：[1，0]，[1，2]，表示如果要选修课程1，必须先选修课程0和课程2。问是否可能把这n门课程都选修一遍。
这个问题看起来相当复杂。难点在于，一门课程可能需要多门课程作为前提条件，这样就很难找到一条可以不重复地遍历所有课程的方法。
比较笨的方法就是先找出那些不需要前提条件的课程，然后由他们出发将那些只需要他们作为前提条件的课程修完。再循环往复。一直到某一次遍历之后，并没有修到新的课程。最后再检查是否还有课程没能修够。这样的话，最坏情况，我们是时间复杂度最坏能达到O(N^3)。使用了unordered_multimap作为辅助工具，代码被Accept了。但是运行时间是最好的coder的10倍。于是，细细研究他人的算法。
2 BFS
其实。这道题难在用一维数据结构来表示这些前提条件，很容易增大时间复杂度。于是，考虑用二维数据结构来表示。
图！而题中给的条件明显是一对多的。那么，适合用邻接链表法表示。采用数据结构vector<unordered_set<int>> map来表示。vector的每个元素表示由某门课程作为前提条件的一组课程。每门课程需要的前提条件可以用一组向量表示vector<int> de。我们用入度称呼这个值，也就是说在图中，进入该节点有多少条路径。那么对于那些不需要前提条件就完成的课程，其入度为0。
BFS法，广度优先。我们先找到一门入度为0的课，然后由它作为前提条件的课程的入度都可以减1，因为这门课程学到了，就等于不需要这个前提条件了。而以它为前提的课程就是该节点的邻接节点。用这种方法，我们每次学到一门课程，N次就可以学完所有的课程，如果某一次没有学到新的课程，那么最终肯定是无法学完的。
上代码：
class Solution {
public:
bool canFinish(int n, vector<pair<int, int>>& pre) {
vector<unordered_set<int> > gra(n);
vector<int> de(n,0);
//make graph
for(auto a:pre)
{
gra[a.second].insert(a.first);
}
//calculate the indegree
for(int i=0;i<n;++i)
{
for(auto a:gra[i])
de[a]++;
}
for(int i=0;i<n;++i)
{
int j=0;
for(;j<n;++j)
{
if(de[j]==0) break;
}
if(j==n) return 0; //this time could not learn a new lesson and we won't make it
de[j]=-1; //in case next time we will learn this lesson again
for(auto a:gra[j])
de[a]--; //any lesson take this lesson as it's prerequisites, it's indegree decrease 1
}
return 1;
}
};
3 DFS
那么DFS（深度优先搜索）是怎么样的思路呢？其实，如果这个图中存在一个环的话，那么肯定无法完成任务。那么什么情况下会完不成任务呢？也就是说1->2，2->3，3->1，也就是说形成了一个环。所以我们把原问题转化为检测图中是否有环。检测环的方法？从某个节点出发，如果又回到该节点，那么此图有环！
我们依次从任意节点出发，遍历该节点可以到达的所有节点，我们用一个向量vector<bool> onePath来记录从该节点出发经过的节点。为了防止重复，我们用变量vector<bool> path记录所有遍历过的节点。
上代码：
class Solution {
public:
bool canFinish(int n, vector<pair<int, int>>& pre) {
vector<unordered_set<int> > gra(n);
vector<bool> path(n,0),onePath(n,0);
//make graph
for(auto a:pre)
{
gra[a.second].insert(a.first);
}
for(int i=0;i<n;++i)
{
if(path[i]) continue;
if(dfs_circle(gra,i,path,onePath))
return 0;
}
return 1;
}
bool dfs_circle(vector<unordered_set<int> >& gra,int node,vector<bool>& path,vector<bool>& onePath)
{
if(onePath[node]==1) return true;
path[node]=onePath[node]=1;
for(auto a:gra[node])
if(dfs_circle(gra,a,path,onePath))
return 1;
onePath[node]=0;
return 0;
}
};
这种转化问题的解法真得很巧妙！太赞！
另外，对于很多条件有交叉的题目，就考虑用图论方法解决，尤其是DFS和BFS算法。