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

}

207, Course schedule

207, Course schedule

====

Topological sort

Coloring

====

1. 給予一個n node number

一個vec<pair<int,int>>prerequest規則

2. prerequest表明<i,j>(有向圖)

如果要access i, 必須先有j

如果規則互斥(產生cycle) 則false

可能有很多方式

可用DFS 可用BFS 可用coloring

3. Coloring比較單純

生成一個map<int, vec<int>> adj來填入規則 //hashMap

->

adj[1].push_back(0)

生成一個vec<int> visited(n,0)來紀錄

如果走的過程中有碰到任何已經拜訪過的

則有cycle, false

否則true

====

class Solution{

public:

bool isCycle(vec<int>visited, vec<vec<int>>adj, int id){

  if visited[id] == 1 return true

  if visited[id] == 0{

    visited[id]=1

    for auto edge:adj[id]

    if isCycle(visited, adj, edge) return true

  }

  visited[id]=2 //?

  return false

}

bool canFinished(int n, vec<vec<int>>& pre){

  map<int, vec<int>> adj

  for auto edge: pre

    adj[edge[1]].push_back(edge[0])

  vec<int> visited(n, 0)

  for auto prule: adj{

    if(isCycle(visited, adj, prule.first)) return false

  }//

return true

}

};