ধরুন আমাদের n প্রসেস আছে, এখানে প্রতিটি প্রসেসের পিআইডি বা প্রসেস আইডি নামে একটি ইউনিক আইডি আছে এবং এর পিপিআইডি (প্যারেন্ট প্রসেস আইডি)ও আছে।
প্রতিটি প্রক্রিয়ার শুধুমাত্র একটি অভিভাবক প্রক্রিয়া আছে, কিন্তু এক বা একাধিক শিশু প্রক্রিয়া থাকতে পারে।
এটি একটি গাছের কাঠামোর মতো। শুধুমাত্র একটি প্রক্রিয়ায় PPID =0 আছে, যার মানে এই প্রক্রিয়াটির কোনো অভিভাবক প্রক্রিয়া নেই। সমস্ত পিআইডি অনন্য ধনাত্মক পূর্ণসংখ্যা হবে।
আমরা প্রক্রিয়াগুলির একটি তালিকা উপস্থাপন করতে দুটি পূর্ণসংখ্যার তালিকা ব্যবহার করব, যেখানে প্রথম তালিকায় প্রতিটি প্রক্রিয়ার জন্য পিআইডি রয়েছে এবং দ্বিতীয় তালিকায় সংশ্লিষ্ট পিপিআইডি রয়েছে। সুতরাং, যদি আমাদের কাছে দুটি তালিকা থাকে, এবং একটি পিআইডি প্রতিনিধিত্ব করে এমন একটি প্রক্রিয়া যা আমরা হত্যা করতে চাই, তাহলে আমাদের প্রক্রিয়াগুলির পিআইডিগুলির একটি তালিকা খুঁজে বের করতে হবে যা শেষ পর্যন্ত মেরে ফেলা হবে। এবং আমাদের অনুমান করা উচিত যে যখন একটি প্রক্রিয়া হত্যা করা হয়, তখন তার সমস্ত শিশু প্রক্রিয়াগুলিকে হত্যা করা হবে৷
সুতরাং, যদি ইনপুট হয় pid =[1, 3, 10, 5] ppid =[3, 0, 5, 3] kill =5, তাহলে আউটপুট হবে [5,10],
কিল 5ও 10 জনকে মেরে ফেলবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি মানচিত্র চাইল্ড সংজ্ঞায়িত করুন
-
n :=পিডের আকার
-
একটি অ্যারে ret সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=0, যখন i
-
u :=ppid[i]
-
v :=pid[i]
-
শিশু[u]
এর শেষে v সন্নিবেশ করান
-
-
একটি সারি q
সংজ্ঞায়িত করুন -
q
-এ কিল সন্নিবেশ করান -
যখন (q খালি নয়), −
করুন-
curr :=q এর প্রথম উপাদান
-
q
থেকে উপাদান মুছুন -
ret এর শেষে curr ঢোকান
-
আরম্ভ করার জন্য i :=0, যখন i <সন্তানের আকার [curr], আপডেট করুন (i 1 দ্বারা বৃদ্ধি করুন), করুন −
-
q
-এ চাইল্ড[curr, i] সন্নিবেশ করান
-
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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, ]
