C++ में सेलिब्रिटी खोजें - स्टैक का उपयोग करके O(n) समाधान

समस्या विवरण

मान लीजिए हमारे पास n लोग हैं (0 से n-1 तक लेबल किए गए) और उनमें से एक सेलिब्रिटी हो सकता है। हम कह सकते हैं कि व्यक्ति x एक सेलिब्रिटी है जब अन्य सभी n-1 लोग x को जानते हैं लेकिन x उनमें से किसी को नहीं जानता। यहां हमें यह ढूंढना है कि सेलिब्रिटी कौन है या सत्यापित करना है कि कोई नहीं है।

हम व्यक्ति 'A' से केवल एक प्रश्न पूछ सकते हैं: "हाय, A. क्या आप B को जानते हैं?" यह जानने के लिए कि A, B को जानता है या नहीं। हमें सेलिब्रिटी ढूंढने के लिए न्यूनतम प्रश्न पूछने हैं। इनपुट के रूप में ग्राफ नामक सूची की सूची है, graph[i][j] = 1 जब i-था व्यक्ति j-था व्यक्ति को जानता है, अन्यथा 0।

उदाहरण के लिए, यदि इनपुट graph = [[1,1,0],[0,1,0],[1,1,1]] है:

तो आउटपुट 1 होगा, क्योंकि सेलिब्रिटी व्यक्ति 1 है क्योंकि 0 और 2 दोनों उसे जानते हैं लेकिन 1 किसी को नहीं जानता।

समाधान दृष्टिकोण

स्टैक का उपयोग करके उम्मीदवार एलिमिनेशन:

1. knows() फ़ंक्शन परिभाषित करें जो a, b लेता है, graph[a][b] लौटाता है
2. एक स्टैक st परिभाषित करें
3. सभी 0 से n-1 व्यक्तियों को st में डालें
4. जब तक st का आकार > 1:
   • x := st का शीर्ष, st से हटाएं
   • y := st का शीर्ष, st से हटाएं
   • यदि knows(x, y) सत्य है, तो y को st में डालें (x सेलिब्रिटी नहीं हो सकता)
   • अन्यथा x को st में डालें (y सेलिब्रिटी नहीं हो सकता)
5. x := st का शीर्ष (संभावित सेलिब्रिटी)
6. सत्यापन: सभी i के लिए 0 से n-1:
   • यदि i == x, तो जारी रखें
   • यदि knows(x, i) सत्य है या knows(i, x) असत्य है, तो -1 लौटाएं
7. 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

आउटपुट

1