สมมติว่ามี n คน (ติดป้าย 0 ถึง n-1) และในกลุ่มอาจมีคนหนึ่งเป็น celebrity เราสามารถบอกได้ว่าคน x เป็น celebrity เมื่อคนอื่น n-1 คนรู้จัก x แต่ x ไม่รู้จักใครเลย ที่นี่เราต้องหาว่าใครคือ celebrity หรือยืนยันว่าไม่มี
เราสามารถถามคำถามเดียวให้คน 'A' ว่า "Hi, A. Do you know B?" เพื่อรับข้อมูลว่า A รู้จัก B หรือไม่ เราต้องถามคำถามน้อยที่สุดเพื่อหา celebrity มีรายการรายการเป็นอินพุทชื่อ graph graph[i][j] = 1 เมื่อคนที่ i รู้จักคนที่ j มิฉะนั้น 0
เช่น ถ้าอินพุทเป็น graph = [[1,1,0],[0,1,0],[1,1,1]]
ผลลัพธ์จะเป็น 1 เนื่องจาก celebrity คือคนที่ติดป้าย 1 เพราะทั้ง 0 และ 2 รู้จักเขา แต่ 1 ไม่รู้จักใคร
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้ −
กำหนดฟังก์ชัน knows() รับ a, b
คืนค่า true เมื่อ graph[a][b] เป็น true
จากเมธอดหลักทำดังนี้ −
กำหนดสแต็ก st
ลูป i := 0 ถึง n-1 ทำ −
แทรก i ลงใน st
ลูป while ขนาดของ st > 1 ทำ −
x := โหนดบนสุดของ st
ลบโหนดออกจาก st
y := โหนดบนสุดของ st
ลบโหนดออกจาก st
ถ้า knows(x, y) เป็นจริง แล้ว −
แทรก y ลงใน st
มิฉะนั้น
แทรก x ลงใน st
x := โหนดบนสุดของ st
ลูป i := 0 ถึง n-1 ทำ −
ถ้า i เท่ากับ x แล้ว −
ข้ามส่วนต่อไป ไปรอบถัดไป
ถ้า knows(x, i) เป็นจริง หรือ knows(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
