Time Needed to Inform All Employees ใน C++ : เวลาระบาดข่าวในองค์กร

บริษัทมีพนักงาน n คน (ID 0..n-1) Head คือ headID Array manager[i] = Manager ตรงๆ ของ i (manager[headID] = -1) โครงสร้างเป็น **Tree**

informTime[i] = นาทีที่ i ใช้แจ้งข่าวให้ **Direct Subordinates ทั้งหมด** (หลังจากเวลานี้ Subordinates ถึงจะเริ่มแจ้งต่อได้) หา **เวลารวมน้อยที่สุด** จน **ทุกคน** ได้รับข่าว

ตัวอย่าง

n=6, headID=2
manager = [2,2,-1,2,2,2]  // ทุกคน Report เข้า 2
informTime = [0,0,1,0,0,0] // Head (2) ใช้ 1 นาทีแจ้งคนอื่น 5 คน

Time = 1 นาที (Head แจ้งเสร็จ ทุกคนรู้แล้ว)
Output: 1

แนวทาง: BFS (Level Order) บน Tree

1. สร้าง **Adjacency List** graph[u] = list of subordinates จาก manager Array
2. หา root = headID
3. BFS จาก Root:
   • Queue เก็บ (node, timeReceived)
   • Pop Node -> สำหรับ Subordinate แต่ละคน: time[sub] = time[node] + informTime[node] Push เข้า Queue
4. คำตอบ = max(time[i]) สำหรับทุก i (เวลาสุดท้ายที่คนสุดท้ายได้รับข่าว)

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) {
        // 1. Build Graph (Tree)
        vector<vector<int>> graph(n);
        for (int i = 0; i < n; i++) {
            if (manager[i] != -1)
                graph[manager[i]].push_back(i);
        }

        // 2. BFS
        queue<int> q;
        q.push(headID);
        vector<int> time(n, 0); // Time when employee receives news
        int maxTime = 0;

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : graph[u]) {
                time[v] = time[u] + informTime[u];
                maxTime = max(maxTime, time[v]);
                q.push(v);
            }
        }
        return maxTime;
    }
};

Input / Output

Input:  6 2 [2,2,-1,2,2,2] [0,0,1,0,0,0]
Output: 1

ความซับซ้อน (Complexity)

• Time: O(N) — Build Graph + BFS Visit Each Node Once
• Space: O(N) — Graph + Queue + Time Array

Alternative: DFS

DFS Recursive คืนค่า Max Time จาก Subtree: dfs(u) = informTime[u] + max(dfs(v) for v in children) ใส่ Base Case Leaf -> 0 ก็ได้ Time O(N) Space O(H) ครับ