Tìm người nổi tiếng trong C ++

Giả sử chúng ta có n người (được đánh dấu từ 0 đến n - 1) và trong số họ, có thể tồn tại một người nổi tiếng. Có thể nói một người x là người nổi tiếng khi tất cả n - 1 người khác biết x nhưng x không biết ai trong số họ. Ở đây, chúng tôi phải tìm ra ai là người nổi tiếng hoặc xác minh rằng không có người đó.

Chúng tôi chỉ được phép hỏi một câu cho người ‘A’, đó là "Xin chào, A. Bạn có biết B không?" để có được thông tin về việc A có biết B hay không. Chúng tôi phải đặt một số câu hỏi tối thiểu để tìm ra người nổi tiếng. Có một danh sách các danh sách dưới dạng đầu vào được gọi là đồ thị, đồ thị [i, j] =1 khi người thứ i biết người thứ j, ngược lại là 0.

Vì vậy, nếu đầu vào giống như graph =[[1,1,0], [0,1,0], [1,1,1]],

thì đầu ra sẽ là 1, vì người nổi tiếng là người được gắn nhãn là 1 vì cả 0 và 2 đều biết anh ta nhưng 1 không biết ai.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một hàm know (), điều này sẽ nhận a, b,
trả về true khi biểu đồ [a, b] là true
Từ phương thức chính, hãy làm như sau -
Xác định một ngăn xếp
để khởi tạo i:=0, khi i
- chèn tôi vào st
trong khi kích thước st> 1, do -
- x:=phần tử hàng đầu của st
- xóa phần tử khỏi st
- y:=phần tử hàng đầu của st
- xóa phần tử khỏi st
- nếu biết (x, y) là đúng thì -
  - chèn y vào st
- Nếu không
  - chèn x vào st
x:=phần tử hàng đầu của st
để khởi tạo i:=0, khi i
- nếu tôi giống với x, thì -
  - Bỏ qua phần sau, chuyển sang phần tiếp theo
- nếu biết (x, i) là đúng hoặc biết (i, x) là sai, thì -
  - trả về -1
trả lại x

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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

Đầu vào

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

Tìm người nổi tiếng trong C ++

Ví dụ

Đầu vào

Đầu ra