C++-এ Find the Celebrity: সেলিব্রিটি খুঁজে বের করা (কমপ্লেক্সিটি অপ্টিমাইজড)

n জন মানুষ (০ থেকে n-1 লেবেলড) আছে, যাদের মধ্যে একজন সেলিব্রিটি থাকতে পারে। সেলিব্রিটি বলতে হলে: অন্য সবাই সেলিব্রিটিকে চিনে, কিন্তু সেলিব্রিটি কাউকেও চিনে না। আমাদের একটি ফাংশন knows(a, b) দিয়ে কেবল এক প্রকার প্রশ্ন জিজ্ঞেস করতে পারি: "A, তুমি কি B কে চিন?"। কমপক্ষে প্রশ্ন করেই সেলিব্রিটি খুঁজে বের করতে হবে। ইনপুট হিসেবে একটি অ্যাডজেসেন্সি ম্যাট্রিক্স graph দেওয়া আছে, যেখানে graph[i][j] = 1 মানে i-তম ব্যক্তি j-তম ব্যক্তিকে চিনে।

উদাহরণ

ইনপুট: graph = [[1,1,0],[0,1,0],[1,1,1]]

আউটপুট: 1 (ব্যক্তি ১ সেলিব্রিটি, কারণ ০ ও ২ তাকে চিনে কিন্তু ১ কাউকেও চিনে না)।

সমাধানের পদ্ধতি (Stack + Verification)

একটি স্ট্যাক st-এ সব ব্যক্তি (০ থেকে n-1) পুশ করুন।
স্ট্যাকের সাইজ ১ হওয়া পর্যন্ত:
- দুইজন x এবং y পপ করুন।
- যদি knows(x, y) সত্য হয়, তবে x সেলিব্রিটি হতে পারে না (কারণ সে কাউকেও চিনে না) → y পুশ করুন।
- অন্যথায় y সেলিব্রিটি হতে পারে না (কারণ সবাই সেলিব্রিটিকে চিনে) → x পুশ করুন।
স্ট্যাকে বাকি থাকা একজন x কে ক্যাডিডেট হিসেবে নিন।
ভেরিফিকেশন: সব i != x এর জন্য, যদি knows(x, i) বা !knows(i, x) হয়, তবে সেলিব্রিটি নেই → -1 রিটার্ন করুন।
সব চেক পাস করলে x রিটার্ন করুন।

C++ কোড উদাহরণ

#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;
    }
};

int main() {
    vector<vector<int>> v = {{1,1,0},{0,1,0},{1,1,1}};
    Solution ob(v);
    cout << (ob.findCelebrity(3));
    return 0;
}

ইনপুট

{{1,1,0},{0,1,0},{1,1,1}} 3