Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

C++ में सेलेब्रिटी का पता लगाएं

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

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

इसलिए, यदि इनपुट ग्राफ़ की तरह है =[[1,1,0],[0,1,0],[1,1,1]],

C++ में सेलेब्रिटी का पता लगाएं

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

  • एक फ़ंक्शन को परिभाषित करें जानता है (), इसमें a, b,

    . लगेगा
  • जब ग्राफ़ [ए, बी] सत्य हो

  • मुख्य विधि से निम्न कार्य करें -

  • एक स्टैक सेंट परिभाषित करें

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • मुझे सेंट में डालें

  • जबकि st> 1 का आकार −

    . करें
    • x:=सेंट का शीर्ष तत्व

    • सेंट से तत्व हटाएं

    • y:=सेंट का शीर्ष तत्व

    • सेंट से तत्व हटाएं

    • यदि जानता है (x, y) सत्य है, तो -

      • सेंट में y डालें

    • अन्यथा

      • सेंट में x डालें

  • x:=सेंट का शीर्ष तत्व

  • इनिशियलाइज़ i:=0 के लिए, जब i

    • अगर मैं x के समान हूं, तो -

      • निम्नलिखित भाग पर ध्यान न दें, अगले पुनरावृत्ति पर जाएं

    • यदि जानता है (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

  1. C++ में एक लाइन के मध्य-बिंदु को खोजने का प्रोग्राम

    इस समस्या में, हमें दो बिंदु A और B दिए गए हैं, जो एक रेखा के आरंभ और अंत बिंदु हैं। हमारा काम C++ में एक लाइन के मध्य-बिंदु को खोजने के लिए एक प्रोग्राम बनाना है। समस्या का विवरण - यहाँ, हमारे पास एक रेखा है जिसमें शुरुआती और अंत बिंदु A(x1, y1) और B(x2, y2) हैं। और हमें रेखा के मध्य-बिंदु को खोजन

  1. C++ में त्रिभुज के केंद्रक को खोजने का कार्यक्रम

    इस समस्या में, हमें एक 2D सरणी दी गई है जो त्रिभुज के तीन शीर्षों के निर्देशांकों को दर्शाती है। हमारा काम C++ में त्रिभुज के Centroid को खोजने के लिए एक प्रोग्राम बनाना है। सेंट्रोइड त्रिभुज का वह बिंदु है जिस पर त्रिभुज की तीन माध्यिकाएं प्रतिच्छेद करती हैं। माध्यिका त्रिभुज की वह रेखा है जो त्र

  1. C++ में समांतर चतुर्भुज का क्षेत्रफल ज्ञात करने का कार्यक्रम

    इस समस्या में, हमें दो मान दिए गए हैं जो समांतर चतुर्भुज के आधार और ऊंचाई को दर्शाते हैं। हमारा कार्य C++ में समांतर चतुर्भुज का क्षेत्रफल ज्ञात करने के लिए एक प्रोग्राम बनाना है। समांतर चतुर्भुज एक चार भुजा बंद आकृति है जिसकी विपरीत भुजाएँ एक दूसरे के समान और समानांतर हैं। समस्या को समझने के लि