Pythonで教える最小人数を見つけるためのプログラム

番号n、「languages」という配列、「friendships」という配列があるとすると、1からnまでの番号が付けられたn個の言語があり、languages [i]はi番目のユーザーが知っている言語のセットを表し、friendships[ i]はペアを保持します[ui、vi]は、ユーザーuiとviの間の友情を示します。 1つの言語を選択して一部のユーザーに教えることで、すべての友達が互いにコミュニケーションできるようになります。教えるために必要な最小ユーザー数を見つける必要があります。 （友情は推移的ではないことを覚えておく必要があります。したがって、xがyの友達であり、yがzの友達である場合、これはxがzの友達であることを意味しません。）

したがって、入力がn =3言語の場合=[[2]、[1,3]、[1,2]、[3]]友情=[[1,4]、[1,2]、[3 、4]、[2,3]]の場合、言語3をユーザー1と3にトレーニングする必要があるため、出力は2になります。これは、教えるユーザーが2人いるため、出力は2です。

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

• lang：=ユーザーが知っているすべての異なる言語セットのリスト
• not_comm：=新しいセット
• 友情のペアa、bごとに、
  • a：=a-1
  • b：=b-1
  • lang[a]とlang[b]が互いに素である場合、
    • not_commにaを挿入
    • bをnot_commに挿入
• not_commが空の場合、
  • 0を返す
• cnt：=空のマップ
• not_commの各人に対して、
  • lang[person]の頻度を保存してcntに保存
• temp：=cntのすべての値のリストの最大値
• not_commの戻りサイズ--temp

例

理解を深めるために、次の実装を見てみましょう-

from collections import Counter
def solve(n, languages, friendships):
   lang = [set(L) for L in languages]

   not_comm = set()
   for a,b in friendships:
      a -= 1
      b -= 1
      if lang[a].isdisjoint(lang[b]):
         not_comm.add(a)
         not_comm.add(b)
   if not not_comm:
      return 0

   cnt = Counter()
   for person in not_comm:
      cnt.update(lang[person])
   temp = max(cnt.values())
   return len(not_comm) - temp

n = 3
languages = [[2],[1,3],[1,2],[3]]
friendships = [[1,4],[1,2],[3,4],[2,3]]
print(solve(n, languages, friendships))

入力

3, [[2],[1,3],[1,2],[3]], [[1,4],[1,2],[3,4],[2,3]]

出力

2