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>()

}

蘿莉銘

蘿莉銘

身不在高，米四就行，胸不在大，有型則靈，斯是蘿莉，為吾是侵。

洋裝貓耳朵，小嘴大眼睛。短髮很俏麗，長髮也飄逸。可以給糖果，玩親親。

無八卦之亂耳，無血拼之勞行。學校游泳室，公園小涼亭。

吾自云：能萌就行

13-02313

13-02313

Others can read the ingredients on a chewing gum wrapper and unlock the secrets of the universe

Some people can read War and Peace and come away thinking 

it's a simple adventure story. 

Others can read the ingredients on a chewing gum wrapper and unlock the secrets of the universe.

<Lex Luthor, Gene Hackman as Lex Luthor - Superman, 1978>

Because Love is the best thing we do.

It was a twisting, turning road that led to the end of the aisle,

and not everything along the way was perfect.

To be honest,

not everything to follow would be perfect either.

But what is?

Here is the secret, kids:

None of us can vow to be perfect.

In the end, all we could do is promise to love each other with everything we've got.

Because Love is the best thing we do.

<How I Met Your Mother, s09ep22, The End of the Aisle>

You will be shocked kids, when you discover how easy it is in life to part ways with people forever.

And that's how it go, kids.

The friends, neighbors, drinking buddies

and partners in crime you love so much when you're young,

as the years go by, you just lose touch.

====

You will be shocked kids,

when you discover how easy it is in life to part ways with people forever.

That's why, when you find someone you want to keep around, you do something about it.

<How I Met Your Mother, s9ep21, Gary Blauman>

Rally

Kids, no matter how hard it try,

even the best of us go a little too wild sometimes.

And in those moments, we all need someone who loves us to help us rally.

Even if that means lying once in a while.

<How I Met Your Mother, s09ep18, Rally>