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.

s思路： 1. 圖。描述兩者之間關(guān)系用edge表示，每個(gè)對(duì)象就是一個(gè)node。首先，把問(wèn)題轉(zhuǎn)化成圖。 2. 看到圖，心里就打顫，遇到的少，心里沒(méi)底。也不是沒(méi)底，是深不可側(cè)，不見(jiàn)底。所以，需要先把心安好，既重視，更要看輕圖，才能學(xué)好圖。 3. 回到圖。先轉(zhuǎn)換圖，把每門(mén)課的所有先修課程和這門(mén)課連接起來(lái)，然后做dfs遍歷，看是否cycle，用dfs時(shí)，就要對(duì)每個(gè)節(jié)點(diǎn)是否visited做標(biāo)記，而且dfs由于是recursive,和其他所有recursive一樣，都有層級(jí)之分。在dfs的visited數(shù)據(jù)結(jié)構(gòu)，需要有三個(gè)狀態(tài)，不同與之前見(jiàn)過(guò)的兩個(gè)狀態(tài)表示是否訪(fǎng)問(wèn)。三個(gè)狀態(tài)分別是：沒(méi)訪(fǎng)問(wèn)，正在訪(fǎng)問(wèn)但沒(méi)訪(fǎng)問(wèn)完成，以及訪(fǎng)問(wèn)完成。“正在訪(fǎng)問(wèn)但沒(méi)訪(fǎng)問(wèn)完成”：表示從這個(gè)節(jié)點(diǎn)出發(fā)進(jìn)入下一個(gè)層次去訪(fǎng)問(wèn)，此時(shí)這個(gè)點(diǎn)確實(shí)被訪(fǎng)問(wèn)了，但是這個(gè)點(diǎn)屬于現(xiàn)在正在訪(fǎng)問(wèn)的path的一個(gè)節(jié)點(diǎn)；“訪(fǎng)問(wèn)完成”表示當(dāng)前點(diǎn)的下一個(gè)層次的遍歷以及完成，注意，下一個(gè)層次包括所有鄰接節(jié)點(diǎn)都訪(fǎng)問(wèn)了，這個(gè)點(diǎn)才算訪(fǎng)問(wèn)完。 4. 寫(xiě)完dfs,發(fā)現(xiàn)圖的dfs的套路和backtracking一毛一樣，都是for+recursive。不同的就是，visited有3中狀態(tài)！ 5. 按理說(shuō)，能用dfs的也可以用bfs，只要能想辦法添加一些輔助量。圖的bfs和其他的bfs一樣，也是一層訪(fǎng)問(wèn)完再訪(fǎng)問(wèn)下一層，而且也用到queue。如果說(shuō)dfs檢查是否有cycle這個(gè)操作就可以表面是否所有課都可以選，那么bfs需要做什么呢？看了答案，很有意思，仍然是檢查是否有cycle,但需利用圖論的知識(shí)：對(duì)每個(gè)節(jié)點(diǎn)的入度(indegree)統(tǒng)計(jì)，然后找到入度為0的所有點(diǎn)放在queue里，每次取出一個(gè)點(diǎn)，找到和其相連的所有節(jié)點(diǎn)，然后把這些節(jié)點(diǎn)的入度減一，表示刪除這條邊，如果某一次刪除，導(dǎo)致入度變成0，那么就把這個(gè)點(diǎn)加入queue,最后等queue為空后，再看所有點(diǎn)的入度是否全為0，如果全為0表示沒(méi)有cycle，否則有cycle。 6. 數(shù)學(xué)原因先不說(shuō)。單說(shuō)思路，仍然是找到邊界這個(gè)方法的應(yīng)用。先統(tǒng)計(jì)所有入度，從入度為0的點(diǎn)入手，這里入度為0的點(diǎn)就是邊界。形象的說(shuō)，一個(gè)圖的入讀為0的點(diǎn)在圖上也一定是在邊緣，只出不進(jìn)，所以是邊緣。值得注意的是，如果沒(méi)有入度為0的點(diǎn)，說(shuō)明這個(gè)圖的所有點(diǎn)都在loop內(nèi)；然后刪除和這個(gè)點(diǎn)相連的節(jié)點(diǎn)之間的連接，同時(shí)入度減一，如果沒(méi)有cycle，最后一定可以把所有所有的入度變成0。所以，根據(jù)這個(gè)條件，就可以判斷是否有cycle了！ 7. 比較一下dfs和bfs區(qū)別:dfs的過(guò)程是在模擬如何去遍歷這個(gè)圖的全過(guò)程；bfs則是模擬如何從圖的邊緣一步一步的把圖給“拆”掉，如果把能拆的都拆了，發(fā)現(xiàn)還有連線(xiàn)，那就是有cycle。一個(gè)是在沿路走；一個(gè)是在把正常的路拆了看留下啥！