求用Python教授的最少人数计算项目

假设我们有一个数字n，一个称为“languages”的数组和一个称为“friendships”的数组，因此有从1到n编号的n种语言，languages [i]表示第i个用户知道的语言集，friendships [i]保存了一对[ui,vi]，表示用户ui和vi之间的友谊关系。我们可以选择一种语言，并将其教授给某些用户，以便所有朋友都可以相互沟通。我们必须找出所需的最小用户数。（有一件事情我们必须记住，友谊关系不是传递性的，因此如果x是y的朋友，y是z的朋友，则这并不意味着x是z的朋友。）

因此，如果输入如下n = 3 languages = [[2], [1,3], [1,2], [3]] friendships = [[1,4], [1,2], [3,4], [2,3]]，那么输出将为2，因为我们需要向用户1和3培训语言3，由于有两个用户需要教授，因此输出为2。

要解决此问题，我们将按照以下步骤进行 –

• lang：所有用户所知道的所有不同语言集的列表
• not_comm：一个新集合
• 对于friendships中的每一对a，b，请执行以下操作
  • a：=a-1
  • b：=b-1
  • 如果lang[a]和lang[b]不相交，则
    • 将a插入not_comm
    • 将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