802, Find eventual safe states

====

802, Find eventual safe states

====

DFS,

cycle find

有向/無向圖找cycle不一樣

有向需要三個顏色(還沒看過/ 還在看/ 已經看完

無向需要兩個顏色(visited/ un-visited

過程中有碰到訪問過/看過的node

就是有cycle

====

a)

1. 題目給予一個graph

定義一個int dp(n, 0)初值

0, 還沒看過

-1,還在看

1,已經看完

2. DFS一進去

先將dp[i]=-1 //還在看

然後針對graph[i][]一一DFS檢查

如果有false則return false

3. 如果graph[i][]跑完 都沒看到cycle 

//如果沒有看到dp==-1, i.e還在看

則dp[i]=1, i.e已經看完

return true

else

return dp[i]==1

4. main一個for跑DFS

如果false,就不加入結果

否則是安全的,加入

====

class Solution{

public:

bool DFS( vec<vec<int>>&graph, vec<int>&dp, int i){

  if ( dp[i] ) //-1 ->false, 1 ->true

    return dp[i]==1

  dp[i]=-1

  for auto t:graph[i].begin; t!=graph[i].end; t++

    if ( !DFS( graph, dp, *t ) )

      return false

  dp[i]=1

  return true;

}

vec<int> eventualSafe( vec<vec<int>>&graph ){

  int n=graph.size()

  vec<int> res

  vec<int> dp(n, 0)

  for i-n

    if( DFS( graph, dp, i )

      res.push_back(i)

  return res

}

}