Chương trình tìm số người tối thiểu cần dạy ngôn ngữ trong Python

Mô tả bài toán

Có n ngôn ngữ, mảng languages[i] là tập ngôn ngữ người i biết. Mảng friendships chứa cặp bạn bè. Chọn một ngôn ngữ dạy cho một số người để mọi cặp bạn bè đều có chung ngôn ngữ. Tìm số người tối thiểu cần dạy.

Ví dụ

n = 3, languages = [[2],[1,3],[1,2],[3]], friendships = [[1,4],[1,2],[3,4],[2,3]] -> đầu ra 2 (dạy ngôn ngữ 3 cho người 1 và 3).

Giải thuật

1. Tìm tập người not_comm không thể giao tiếp với bạn bè (không có ngôn ngữ chung).
2. Nếu rỗng -> trả về 0.
3. Đếm tần suất ngôn ngữ trong nhóm not_comm.
4. Chọn ngôn ngữ phổ biến nhất, dạy cho những người còn lại trong not_comm.
5. Kết quả = |not_comm| - max_frequency.

Triển khai Python

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