ধরুন আমাদের n লোক আছে (0 থেকে n - 1 পর্যন্ত লেবেলযুক্ত) এবং তাদের মধ্যে একজন সেলিব্রিটি থাকতে পারে। আমরা বলতে পারি একজন ব্যক্তি x একজন সেলিব্রিটি যখন অন্য সব n - 1 জন মানুষ x জানে কিন্তু x তাদের কাউকেই জানে না। এখানে আমাদের খুঁজে বের করতে হবে সেলিব্রিটি কে বা যাচাই করতে হবে যে সেখানে কেউ নেই।
আমাদের 'ক' ব্যক্তিকে শুধুমাত্র একটি প্রশ্ন জিজ্ঞাসা করার অনুমতি দেওয়া হয়েছে, যে "হাই, এ। আপনি কি বি জানেন?" ক খ জানে কি না তার তথ্য পেতে। সেলিব্রিটি খুঁজে বের করার জন্য আমাদের ন্যূনতম সংখ্যক প্রশ্ন জিজ্ঞাসা করতে হবে। ইনপুট হিসাবে তালিকার একটি তালিকা রয়েছে যাকে গ্রাফ বলা হয়, গ্রাফ[i,j] =1 যখন ith ব্যক্তি jth ব্যক্তিকে জানে, অন্যথায় 0।
সুতরাং, যদি ইনপুট গ্রাফের মত হয় =[[1,1,0],[0,1,0],[1,1,1]],
তাহলে আউটপুট হবে 1, কারণ সেলিব্রিটি হল 1 হিসাবে লেবেল করা ব্যক্তি কারণ 0 এবং 2 উভয়েই তাকে চেনে কিন্তু 1 কাউকে চেনে না৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
একটি ফাংশন জানেন(), এটি একটি, বি,
লাগবে -
গ্রাফ[a, b] সত্য
হলে true ফেরত দিন -
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
একটি স্ট্যাক স্ট্যাক সংজ্ঞায়িত করুন
-
আরম্ভ করার জন্য i :=0, যখন i
-
আমাকে st
-এ ঢোকান
-
-
যখন st> 1 এর আকার, −
করুন-
x :=st
এর শীর্ষ উপাদান -
st
থেকে উপাদান মুছুন -
y :=st
এর শীর্ষ উপাদান -
st
থেকে উপাদান মুছুন -
যদি জানে(x, y) সত্য, তাহলে −
-
st
-এ y ঢোকান
-
-
অন্যথায়
-
st
-এ x ঢোকান
-
-
-
x :=st
এর শীর্ষ উপাদান -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি আমি x এর মত হয়, তাহলে −
-
নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তি এড়িয়ে যান
-
-
যদি knows(x, i) সত্য হয় বা জানে(i, x) মিথ্যা হয়, তাহলে −
-
রিটার্ন -1
-
-
-
রিটার্ন x
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
vector<vector<int<> graph;
public:
Solution(vector<vector<int<> &graph){
this->graph = graph;
}
bool knows(int a, int b){
return graph[a][b];
}
int findCelebrity(int n) {
stack<int< st;
for (int i = 0; i < n; i++) {
st.push(i);
}
while (st.size() > 1) {
int x = st.top();
st.pop();
int y = st.top();
st.pop();
if (knows(x, y)) {
st.push(y);
}
else {
st.push(x);
}
}
int x = st.top();
for (int i = 0; i < n; i++) {
if (i == x)
continue;
if (knows(x, i) || !knows(i, x)) {
return -1;
}
}
return x;
}
};
main(){
vector<vector<int<> v = {{1,1,0},{0,1,0},{1,1,1}};
Solution ob(v);
cout << (ob.findCelebrity(3));
} ইনপুট
{{1,1,0},{0,1,0},{1,1,1}}
3 আউটপুট
1
