C++ में सभी कर्मचारियों को सूचित करने के लिए आवश्यक समय

मान लीजिए कि हमारे पास एक कंपनी है जिसमें प्रत्येक कर्मचारी के लिए एक विशिष्ट आईडी के साथ n कर्मचारी हैं। ये आईडी 0 से n - 1 तक होती हैं। कंपनी का मुखिया हेडआईडी वाला होता है। प्रत्येक कर्मचारी के पास प्रबंधक सरणी में दिया गया एक प्रत्यक्ष प्रबंधक होता है जहां प्रबंधक [i] i-वें कर्मचारी का प्रत्यक्ष प्रबंधक होता है, प्रबंधक [हेडआईडी] =-1। यह भी गारंटी है कि अधीनता संबंधों में पेड़ जैसी संरचना होती है। यहां कंपनी के प्रमुख कंपनी के सभी कर्मचारियों को एक जरूरी खबर के बारे में सूचित करना चाहते हैं। वह अपने प्रत्यक्ष अधीनस्थों को सूचित कर सकता है और जब तक सभी कर्मचारियों को तत्काल समाचार के बारे में पता नहीं चल जाता है, तब तक वे अपने अधीनस्थों को सूचित करेंगे। i-वें कर्मचारी को अपने सभी प्रत्यक्ष अधीनस्थों को सूचित करने के लिए सूचना समय [i] मिनटों की आवश्यकता होती है (इसलिए सूचना समय [i] मिनट के बाद, उसके सभी प्रत्यक्ष अधीनस्थ समाचार फैलाना शुरू कर सकते हैं)। हमें सभी कर्मचारियों को तत्काल समाचार के बारे में सूचित करने के लिए आवश्यक मिनटों की संख्या का पता लगाना होगा। तो अगर इनपुट n =6, हेडआईडी =2, मैनेजर =[2,2,-1,2,2,2], इनफ्रॉमटाइम =[0,0,1,0,0,0,0] की तरह है, तो आउटपुट 1 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• रिट:=0

• एक सरणी को परिभाषित करें जिसे आकार n का ग्राफ कहा जाता है, रूट सेट करें:=-1

• मैं के लिए 0 से लेकर प्रबंधक सरणी के आकार तक

  • यू:=मैनेजट[i] और वी:=मैं

  • यदि आप -1 है, तो रूट सेट करें:=v, और अगले पुनरावृत्ति के लिए जाएं

  • ग्राफ़ में v डालें[u]

• एक कतार q को परिभाषित करें, q में रूट डालें, और एक सरणी को परिभाषित करें जिसे समय कहा जाता है, आकार n

• जब तक q खाली न हो

  • curr :=q का अगला तत्व, और q से सामने वाले तत्व को हटा दें

  • यदि ग्राफ़ की सूची का आकार [कर] 0 है, तो अगले पुनरावृत्ति पर जाएं

  • मैं के लिए ग्राफ़ की सूची के आकार के लिए 0 श्रेणी में [curr]

    • q में ग्राफ़ [curr, i] डालें

    • समय [ग्राफ [कर्र, आई]]:=समय [कर्र] + सूचना समय [कर्र]

• मेरे लिए 0 से n - 1:रिट:=अधिकतम रिट और समय [i]

• वापसी रिट

उदाहरण (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