मान लीजिए हमारे पास n प्रोसेस हैं, यहां प्रत्येक प्रोसेस की एक अद्वितीय आईडी होती है जिसे PID या प्रोसेस आईडी कहा जाता है और इसका PPID (पैरेंट प्रोसेस आईडी) भी होता है।
प्रत्येक प्रोसेस का केवल एक पैरेंट प्रोसेस होता है, लेकिन उसके एक या अधिक चाइल्ड प्रोसेस हो सकते हैं।
यह एक ट्री संरचना की तरह है। केवल एक प्रोसेस का PPID = 0 होता है, जिसका अर्थ है कि इस प्रोसेस का कोई पैरेंट प्रोसेस नहीं है। सभी PID अद्वितीय धनात्मक पूर्णांक होंगे।
हम प्रोसेस की सूची को दर्शाने के लिए पूर्णांकों की दो सूचियों का उपयोग करेंगे, जहां पहली सूची प्रत्येक प्रोसेस के लिए PID रखती है और दूसरी सूची संबंधित PPID रखती है। तो, यदि हमारे पास दो सूचियां हैं, और एक PID जो उस प्रोसेस को दर्शाता है जिसे हम मारना चाहते हैं, तो हमें उन प्रोसेस की PID की सूची ढूंढनी होगी जो अंत में मारे जाएंगे। और हमें मान लेना चाहिए कि जब एक प्रोसेस मारा जाता है, तो उसके सभी चाइल्ड प्रोसेस भी मारे जाएंगे।
उदाहरण के लिए, यदि इनपुट pid = [1, 3, 10, 5], ppid = [3, 0, 5, 3], kill = 5 है, तो आउटपुट [5,10] होगा।
हल करने की विधि
हम BFS का उपयोग करेंगे:
- चाइल्ड मैप परिभाषित करें।
- n = pid का आकार।
- प्रत्येक i के लिए, u = ppid[i], v = pid[i], child[u] में v जोड़ें।
- कतार q परिभाषित करें, kill डालें।
- जब तक q खाली न हो: वर्तमान निकालें, परिणाम में जोड़ें, उसके बच्चों को q में डालें।
- परिणाम लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) { map<int, vector<int> > child; int n = pid.size(); vector<int> ret; for (int i = 0; i < n; i++) { int u = ppid[i]; int v = pid[i]; child[u].push_back(v); } queue<int> q; q.push(kill); while (!q.empty()) { int curr = q.front(); q.pop(); ret.push_back(curr); for (int i = 0; i < child[curr].size(); i++) { q.push(child[curr][i]); } } return ret; } }; main(){ Solution ob; vector<int> v = {1,3,10,5}, v1 = {3,0,5,3}; print_vector(ob.killProcess(v, v1, 5)); }
इनपुट
{1,3,10,5},{3,0,5,3},5
आउटपुट
[5, 10, ]
