Chương trình đếm số bạn bè không vui trong Python

Cho preferences[i] = danh sách bạn bè ưu tiên của người i (giảm dần). Các cặp pairs[i]=[x,y] (đã ghép đôi). Người x không vui nếu ghép với y nhưng tồn tại u ghép với v sao cho: x thích u hơn y VÀ u thích x hơn v. Đếm số người không vui.

Ví dụ: preferences=[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs=[[0,1],[2,3]] → 2 (người 1 và 3 không vui).

Giải thuật (Xây đồ thị ưu tiên)

1. Xây đồ thị graph[u][v] = 1 nếu u thích v hơn bạn đôi hiện tại.
2. Với mỗi cặp (s,e):
   • Duyệt pref trong preferences[s] cho đến gặp e: graph[s][pref] = 1.
   • Tương tự cho e.
3. Đếm không vui: với mỗi cặp (s,e), nếu tồn tại pref trong graph[s] mà graph[pref][s] tồn tại → s không vui. Tương tự cho e.

Ví dụ minh họa

from collections import defaultdict

def solve(preferences, pairs):
    graph = defaultdict(dict)
    for start, end in pairs:
        for pref in preferences[start]:
            if pref == end:
                break
            graph[start][pref] = 1
        for pref in preferences[end]:
            if pref == start:
                break
            graph[end][pref] = 1
    unhappy = 0
    for start, end in pairs:
        for pref in graph[start]:
            if graph[pref].get(start):
                unhappy += 1
                break
        for pref in graph[end]:
            if graph[pref].get(end):
                unhappy += 1
                break
    return unhappy

preferences = [[1,2,3],[3,2,0],[3,1,0],[1,2,0]]
pairs = [[0,1],[2,3]]
print(solve(preferences, pairs))

Đầu vào

[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], [[0,1],[2,3]]

Đầu ra

2