1376, Time needed to inform all employees

====

1376, Time needed to inform all employees

====

DFS,

Time taken to reach all nodes, or share info to all graph nodes

====

1. 題目給予一個vec<int> manager

=>

生成一份vec<vec<int>> children

or

map<int, vec<int>> children

children用意在紀錄node擁有的child

(可視為hash map

2. 因為children會紀錄所mana<->child關係

所以從root(題目給的headID) 開始DFS

會走過所有node

3. 題目給予一個 vec<int>informTime

定義一個resource 為最終total結果

每次DFS,

一個current為加上目前informTime[i]的時間

每次DFS 比較max(resource, current)

最終return resource

====

class Solution{

int DFS( vec<vec<int>>&child, int node, vec<int>&time){

if child[node].size == 0

  return 0

  //本次node沒有children, time沒有增加, return

int ans= time[node]

int tempMax= 0

for(auto c: child[node]){

  tempMax = max( tempMax, DFS( child, c, informTime)

//如果child有多個 會停在for裡面

//當有找到更大的結果 會丟給tempMax

//當次還沒return就不會被清零

//清零用意只是紀錄當次node子集裡的最大

}

return ans+tempMax

//結果等於 當前的time[node] 

//加上

//子集裡面最大的time

}

public:

int numOfMinute( int n, int headID, vec<int>& manager, vec<int>& informTime){

vec<vec<int>> children(n)

for int i=0; i<n; i++

  if manager[i] != -1

    children[ manager[i] ].push_back(i)

return DFS( children, headID, informTime )

}