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

}

};