C++で有名人を探す

n人（0からn-1のラベルが付いている）がいて、その中に1人の有名人がいるとします。他のすべてのn-1人がxを知っているが、xはそれらのいずれも知らない場合、人xは有名人であると言えます。ここでは、有名人が誰であるかを見つけるか、有名人がいないことを確認する必要があります。

人物「A」に「こんにちは、A。Bを知っていますか？」という質問を1つだけ許可されています。 AがBを知っているかどうかの情報を取得します。有名人を見つけるには、最小限の質問をする必要があります。グラフと呼ばれる入力としてリストのリストがあります。i番目の人がj番目の人を知っている場合はgraph[i、j] =1、それ以外の場合は0です。

したがって、入力がgraph =[[1,1,0]、[0,1,0]、[1,1,1]]、

0と2の両方が彼を知っているが、1は誰も知らないため、有名人は1とラベル付けされた人物であるため、出力は1になります。

これを解決するには、次の手順に従います-

• 関数knows（）を定義します。これにはa、b、

  が必要です。

• グラフ[a、b]がtrueの場合はtrueを返します

• メインの方法から、次のようにします-

• 1つのスタックstを定義する

• 初期化i：=0の場合、i

  • iをstに挿入

• st> 1のサイズで、実行-

  • x：=stの最上位要素

  • stから要素を削除

  • y：=stの最上位要素

  • stから要素を削除

  • knows（x、y）が真の場合、-

    • yをstに挿入

  • それ以外の場合

    • xをstに挿入

• x：=stの最上位要素

• 初期化i：=0の場合、i

  • iがxと同じ場合、-

    • 次の部分を無視し、次の反復にスキップします

  • knows（x、i）がtrueまたはknows（i、x）がfalseの場合、-

    • -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