ধরুন একটি কোম্পানিতে n কর্মী আছে যারা 0 থেকে n - 1 পর্যন্ত ইউনিক ID রাখে। কোম্পানির প্রধান headID। প্রতিটি কর্মীর এক ডায়রেক্ট ম্যানেজার আছে manager অ্যারেতে দেওয়া, যেখানে manager[i] i-তম কর্মীর ডায়রেক্ট ম্যানেজার, manager[headID] = -1। এছাড়া গ্যারান্টি আছে যে সাবঅর্ডিনেশন রিলেশনশিপ ট্রি-লিক স্ট্রাকচার। কোম্পানির প্রধান সব কর্মীকে একটি জরুরি খবর জানাতে চান। সে তার ডায়রেক্ট সাবঅর্ডিনেটদের জানাবে, তারা তাদের সাবঅর্ডিনেটদের জানাবে এবং এভাবে চলবে যতক্ষণ না সবাই জানে। i-তম কর্মী তার সকল ডায়রেক্ট সাবঅর্ডিনেটকে জানাতে informTime[i] মিনিট নেয় (তাই informTime[i] মিনিট পরে তার সাবঅর্ডিনেটরা খবর ছড়িয়ে দিতে শুরু করবে)। সকল কর্মীকে খবর দেওয়ার জন্য প্রয়োজনীয় মিনিটের সংখ্যা বের করতে হবে। ইনপুট n = 6, headID = 2, manager = [2,2,-1,2,2,2], informTime = [0,0,1,0,0,0] হলে আউটপুট হবে ১।
সমাধানের ধাপগুলো:
ret := 0
সাইজ n-এর একটি graph অ্যারে ডিফাইন করুন, root := -1 সেট করুন
i = 0 থেকে manager array-এর সাইজ পর্যন্ত লুপ চালান
u := manager[i], v := i
যদি u == -1 হয়, তবে root := v সেট করুন এবং পরবর্তী ইটারেশনে যান
graph[u]-তে v ইনসার্ট করুন
একটি কিউ q ডিফাইন করুন, q-তে root ইনসার্ট করুন, এবং সাইজ n-এর একটি time অ্যারে ডিফাইন করুন
যখন q খালি নয়
curr := q-এর ফ্রন্ট এলিমেন্ট, q থেকে পপ করুন
যদি graph[curr]-এর সাইজ 0 হয়, তবে পরবর্তী ইটারেশনে যান
i = 0 থেকে graph[curr]-এর সাইজ পর্যন্ত লুপ চালান
graph[curr][i] q-তে পশ করুন
time[graph[curr][i]] := time[curr] + informTime[curr]
i = 0 থেকে n – 1 পর্যন্ত: ret := max(ret, time[i])
ret রিটার্ন করুন
উদাহরণ (C++)
নিচের ইমপ্লিমেন্টেশন দেখুন ভালো বুঝতে −
#include <bits/stdc++.h> using namespace std; class Solution { public: int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) { int ret = 0; vector <int> graph[n]; int root = -1; for(int i = 0; i < manager.size(); i++){ int u = manager[i]; int v = i; if(u == -1) { root = v; continue; } graph[u].push_back(v); } queue <int> q; q.push(root); vector <int> time(n); while(!q.empty()){ int curr = q.front(); q.pop(); if(!graph[curr].size()) continue; for(int i = 0; i < graph[curr].size(); i++){ q.push(graph[curr][i]); time[graph[curr][i]] = time[curr] + informTime[curr]; } } for(int i = 0; i <n; i++)ret = max(ret, time[i]); return ret; } }; main(){ vector<int> v = {2,2,-1,2,2,2}, v1 = {0,0,1,0,0,0}; Solution ob; cout << (ob.numOfMinutes(6, 2, v, v1)); }
ইনপুট
6 2 [2,2,-1,2,2,2] [0,0,1,0,0,0]
আউটপুট
1
