ค้นหาคนดังใน C++

สมมติว่าเรามี n คน (ตั้งแต่ 0 ถึง n - 1) และในจำนวนนั้น อาจมีคนดังอยู่คนหนึ่ง เราสามารถพูดได้ว่าคน x เป็นคนดังเมื่อคนอื่น n - 1 คนรู้จัก x แต่ x ไม่รู้จักพวกเขาเลย ที่นี่เราต้องค้นหาว่าใครคือคนดังหรือยืนยันว่าไม่มี

เราได้รับอนุญาตให้ถามคำถามกับคน 'A' ได้เพียงคำถามเดียวว่า "สวัสดี ก. คุณรู้จัก B หรือไม่" เพื่อให้ได้ข้อมูลว่า A รู้ B หรือไม่ เราต้องถามคำถามจำนวนขั้นต่ำเพื่อค้นหาคนดัง มีรายการของรายการเป็นอินพุตที่เรียกว่ากราฟ กราฟ[i,j] =1 เมื่อบุคคลรู้จักบุคคลที่ j หรือ 0

ดังนั้น หากอินพุตเป็นเหมือนกราฟ =[[1,1,0],[0,1,0],[1,1,1]],

จากนั้นผลลัพธ์จะเป็น 1 เนื่องจากคนดังคือบุคคลที่ถูกระบุว่าเป็น 1 เพราะทั้ง 0 และ 2 รู้จักเขา แต่ 1 ไม่รู้จักใครเลย

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชั่น Know() นี้จะใช้เวลา a, b,

• คืนค่า จริง เมื่อ graph[a, b] เป็นจริง

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• กำหนดหนึ่งสแต็ก st

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ใส่ i ลงใน st

• ในขณะที่ขนาดของ st> 1 ทำ −

  • x :=องค์ประกอบด้านบนของ st

  • ลบองค์ประกอบออกจาก st

  • y :=องค์ประกอบด้านบนของ st

  • ลบองค์ประกอบออกจาก st

  • ถ้า know(x, y) เป็นจริง ดังนั้น −

    • ใส่ y ลงใน st

  • มิฉะนั้น

    • ใส่ x ลงใน st

• x :=องค์ประกอบด้านบนของ st

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้าฉันเหมือนกับ x แล้ว −

    • ละเว้นส่วนต่อไปนี้ ข้ามไปยังการทำซ้ำถัดไป

  • ถ้า know(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