210, Course Schedule 2

210, Course Schedule 2

====

Topological sort

====

1. 給予一個node_number, 一個規則preReq vec<vec<>>

建立一個graph vec<vec<>>來紀錄topo //父子關係

2. 建立一個indegree

根據先後的規則 for紀錄每個node的深度

//聰明, 深度加在preReq的頭元素, 原則越多越深

//深度為0就是必須第一個走在前面的

3. 建立一個Queue nodes 存放走訪的點的順序,

//深度為0 加入queue

一個Int visit紀錄走過的點的數量, 判斷最終走過的點是不是全部點數量

//不是 則有cycle

4. 每當queue不為空

pop, push_back到ret

->

當次元素pop掉後, 去graph找接著的topo元素是哪些

->

這些topo元素, indegree -1

如果degree變0, 表示接著可以處理了, 加入queue

====

vec<int> findOrder(int numCourse, vector<pair<int, int>>& prerequest){

vec<vec<int>> graph(numCourse, vec<int>() )

vec<int> indegree(numCourse, 0)

queue<int> nodesQ

int visited=0

vec<int> ret

for( auto eq: prerequest ){

  graph[eq.second].push_back( eq.first )

  indegree[eq.first]++

}

for( int n, n<numCourse, n++)

  if(indegree[n] == 0)

    nodeQ.push(n)

while(!nodeQ.empty()){

  visited++

  int nid = nodeQ.front()

  nodeQ.pop()

  ret.push_back(nid)

  for( auto topo:graph[nid] ){

    indegree[topo]--

    if(indegree[topo]==0)

      nodeQ.push(topo)

  }

}//while empty

return visited==numCourse ? ret : vec<int>()

}