Find the Celebrity - Tìm người nổi tiếng (celebrity) trong nhóm

Cho n người (0..n-1), có thể có 1 celebrity: mọi người khác biết celebrity, nhưng celebrity không biết ai. Chỉ được hỏi knows(A,B). Tìm celebrity hoặc trả -1.

Ví dụ: graph=[[1,1,0],[0,1,0],[1,1,1]] → celebrity là 1.

Giải thuật (Loại trừ bằng stack / Hai con trỏ)

Đưa tất cả vào stack. Lặp: lấy 2 người x,y. Nếu knows(x,y) thì x không phải celebrity → đẩy y lại. Ngược lại đẩy x. Cuối cùng candidate = stack.top(). Xác thực: candidate không biết ai, và mọi người khác biết candidate.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
    vector<vector<int>> graph;
public:
    Solution(vector<vector<int>>& g) : graph(g) {}
    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;
}

Đầu vào

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

Đầu ra

1