Chương trình tìm số người tối thiểu để dạy bằng Python

Giả sử chúng ta có một số n, một mảng được gọi là 'ngôn ngữ' và một mảng được gọi là 'tình bạn', vì vậy có n ngôn ngữ được đánh số từ 1 đến n, các ngôn ngữ [i] đại diện cho một tập hợp các ngôn ngữ mà người dùng thứ i biết và tình bạn [ i] giữ một cặp [ui, vi] biểu thị tình bạn giữa người dùng ui và vi. Chúng tôi có thể chọn một ngôn ngữ và dạy nó cho một số người dùng để tất cả bạn bè có thể giao tiếp với nhau. Chúng tôi phải tìm số lượng người dùng tối thiểu cần thiết để dạy. (Một điều chúng ta phải nhớ rằng tình bạn không có tính bắc cầu, vì vậy nếu x là bạn của y và y là bạn của z, điều này không có nghĩa là x là bạn của z).

Vì vậy, nếu đầu vào là n =3 ngôn ngữ =[[2], [1,3], [1,2], [3]] tình bạn =[[1,4], [1,2], [3 , 4], [2,3]], thì đầu ra sẽ là 2 vì chúng ta cần đào tạo ngôn ngữ 3 cho người dùng 1 và 3, vì có hai người dùng để dạy nên đầu ra là 2.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• lang:=danh sách tất cả các nhóm ngôn ngữ riêng biệt mà người dùng biết
• not_comm:=một tập hợp mới
• đối với mỗi cặp a, b trong quan hệ bạn bè, hãy thực hiện
  • a:=a - 1
  • b:=b - 1
  • nếu lang [a] và lang [b] không rời nhau, thì
    • chèn một vào not_comm
    • chèn b vào not_comm
• nếu not_comm trống, thì
  • trả về 0
• cnt:=một bản đồ trống
• đối với mỗi người trong not_comm, hãy thực hiện
  • lưu trữ tần suất của lang [person] và lưu trữ vào cnt
• temp:=tối đa danh sách tất cả các giá trị của cnt
• kích thước trả lại của not_comm - tạm thời

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

2