C++で有名人問題を解く：スタックを使った効率的なアルゴリズム

n人の人（0からn-1までのラベル付き）がいて、その中に「有名人」が1人存在する可能性があるとします。人xが有名人であるとは、他のn-1人全員がxを知っている一方で、xは彼らの誰一人として知らないことを指します。この課題では、有名人が誰であるかを見つけるか、あるいは有名人が存在しないことを確認します。

情報を得るために許されているのは、人Aに対して「Aさん、Bさんのことを知っていますか？」と質問することだけです。有名人を特定するには、質問の回数を最小限に抑える必要があります。入力はgraphというリストのリストで与えられ、i番目の人がj番目の人を知っている場合はgraph[i][j] = 1、そうでなければ0となります。

例えば、入力がgraph = [[1,1,0],[0,1,0],[1,1,1]]のような場合、出力は1になります。有名人はラベル1の人物だからです。0と2の両方が彼を知っている一方で、1自身は誰も知りません。

この問題を解くために、以下の手順に従います。

• 関数knows()を定義します。引数はaとbです。
• graph[a][b]がtrueであればtrueを返します。
• メインメソッドでは以下の処理を行います。
• スタックstを1つ定義します。
• i := 0で初期化し、i < nの間、iを1ずつ増やしながら繰り返します。
  • iをstに挿入します。
• stのサイズが1より大きい間、以下を繰り返します。
  • x := stの先頭要素を取り出し、stから削除します。
  • y := stの先頭要素を取り出し、stから削除します。
  • knows(x, y)がtrueであれば、yをstに挿入します。
  • そうでなければ、xをstに挿入します。
• x := stの先頭要素とします。
• i := 0で初期化し、i < nの間、iを1ずつ増やしながら繰り返します。
  • iがxと等しい場合は、その後の処理をスキップして次の反復へ進みます。
  • knows(x, i)がtrue、またはknows(i, x)がfalseの場合は、-1を返します。
• xを返します。

このアルゴリズムの計算量はO(n)です。スタックによる絞り込みフェーズでは、1回の比較ごとに必ず1人が候補から除外されるため、質問回数を最小限に抑えながら有名人の候補を1人に絞り込むことができます。最後に残った候補が本当に有名人かどうかを、全員に対して検証している点もポイントです。

例

より理解を深めるために、以下の実装例を見てみましょう。

#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