会議に招待できる従業員の最大数

2127。会議に招待される最大の従業員

難易度：hard

トピック：深さ第一検索、グラフ、トポロジーソート

会社が会議を開催しており、n従業員のリストがあり、招待されるのを待っています。彼らは、従業員の任意の数字

を席にすることができる大きな円形のテーブルを手配しました。

従業員には0からn -1に番号が付けられています。各従業員にはお気に入りの人がいます。テーブル。従業員のお気に入りの人は、

ではありません a 0インデックスinteger配列のお気に入りが与えられます。会議に招待できる従業員。

例1：

入力：お気に入り= [2,2,1,2]

output：3

説明：

• 上記の図は、会社が従業員を0、1、および2に招待し、丸いテーブルに着席する方法を示しています。 従業員2は従業員0、1、および3のそばに座ることができないため、すべての従業員を招待することはできません。 会社は従業員を1、2、および3に招待し、希望する席を与えることができることに注意してください。
会議に招待できる従業員の最大数は3です。
• 例2：
  input：
  • お気に入り= [1,2,0]
  output：
  • 3
説明：

各従業員は、少なくとも1人の他の従業員のお気に入りの人物であり、会社が招待できる唯一の方法は、すべての従業員を招待することです。 座席配置は、例1に示されている図の配置と同じになります。

従業員0は従業員2と1の間に座ります

従業員1は従業員0と2の間に座ります
• 従業員2は従業員1と0の間に座ります
会議に招待できる従業員の最大数は3です。
• 例3：
• • input：お気に入り= [3,0,1,4,1]
  • output：4
  • 説明：
    • 上記の図は、会社が従業員をどのように招待し、4、1、3、および4を招待し、丸いテーブルに座っているかを示しています。
    従業員2は、お気に入りの従業員1の隣の2つのスポットが取られているため、招待できません。
    • それで、会社は彼らを会議から除外します。
    • 会議に招待できる従業員の最大数は4です。
  制約：

  n ==お気に入り。length

  2＆lt; = n＆lt; = 10
  • 5
  • ^{0＆lt; =お気に入り[i]＆lt; = n -1}
  お気に入り[i]！= i
  • ヒント：

  特定の配列のお気に入りから、インデックスIごとにグラフを作成します。これには、お気に入り[i]からiまでの方向性があります。グラフは、サイクルと非環境エッジの鎖の組み合わせになります。さて、私たちがテーブルに座るために従業員を選ぶことができる方法は何ですか？

  従業員を選択できる最初の方法は、グラフのサイクルを選択することです。この場合、サイクルに嘘をついていない従業員は、テーブルには決して座ることができないことが証明できます（サイクルの長さは2の場合を除く）。
  2番目の方法は、非環式チェーンを組み合わせることです。最大の2つのチェーンは、各チェーンがサイクル内の従業員の1人で終了する長さ2のサイクルで組み合わせることができます。
  2. 解決策：
  ソリューションには、お気に入りの配列によって形成されたグラフ内のサイクルとチェーンの分析が含まれます。
  このソリューションをPHP：

  2127に実装しましょう。会議に招待される最大の従業員

  説明：

  グラフ表現
  ：

  <?php /**
   * @param Integer[] $favorite
   * @return Integer
   */
  function maximumInvitations($favorite) {
      ...
      ...
      ...
      /**
       * go to ./solution.php
       */
  }
  
  // Example usage:
  $favorites1 = [2, 2, 1, 2];
  $favorites2 = [1, 2, 0];
  $favorites3 = [3, 0, 1, 4, 1];
  
  echo maximumInvitations($favorites1) . "\n"; // Output: 3
  echo maximumInvitations($favorites2) . "\n"; // Output: 3
  echo maximumInvitations($favorites3) . "\n"; // Output: 4
  ?>
  

  各従業員がお気に入りを指し、指示されたグラフを形成します。

  アレイのINDEGREは、従業員が各人に何人を指しているかを追跡するために使用されます。

  1. チェーンのトポロジーソート

     ：
     着信エッジのない従業員（indegree = 0）は、サイクルにつながるチェーンの長さを計算するために処理されます。
  2. サイクル検出

     ： サイクルを検出するために、

     従業員が訪問されます。サイクルが見つかったら：
     長さ2のサイクルの場合、サイクルの各ノードに取り付けられたチェーンがマージされます。
     • サイクルが長くなると、サイクル全体の長さが考慮されます。

  3. result
     ：
     • • すべてのサイクル長の最大値と、2長サイクルからのマージされたチェーンの長さの合計が返されます。
       このアプローチにより、
     o（n）
  の時間の複雑さで効率が保証され、

  4. 105

     。
     • 連絡先リンク
  このシリーズが役立つと思った場合は、

  リポジトリをGithubでスターに提供するか、お気に入りのソーシャルネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味があります！

  このようなもっと役立つコンテンツが必要な場合は、お気軽にフォローしてください：

  • linkedIn
  • github

以上が会議に招待できる従業員の最大数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。