โปรแกรมนับจำนวนเพื่อนที่ไม่พอใจใน Python

ปัญหา

มี preferences รายการความชอบเพื่อน (index น้อย = ชอบมาก) และ pairs คู่เพื่อน เพื่อน x ไมพอใจถ้า: x คู่กับ y แต่มี u คู่กับ v ที่ x ชอบ u กว่า y และ u ชอบ x กว่า v หาจำนวนเพื่อนไม่พอใจ

ตัวอย่าง

preferences=[[1,2,3],[3,2,0],[3,1,0],[1,2,0]], pairs=[[0,1],[2,3]] → 2 (เพื่อน 1 และ 3 ไมพอใจ)

ขั้นตอนการแก้ปัญหา

1. graph := defaultdict(dict)
2. สำหรับ (start, end) ใน pairs:
   • สำหรับ pref ใน preferences[start] จนกว่าจะเจอ end: graph[start][pref] = 1
   • สำหรับ pref ใน preferences[end] จนกว่าจะเจอ start: graph[end][pref] = 1
3. unhappy := 0
4. สำหรับ (start, end) ใน pairs:
   • ถ้า graph[pref].get(start) สำหรับ pref ใน graph[start]: unhappy += 1
   • ถ้า graph[pref].get(end) สำหรับ pref ใน graph[end]: unhappy += 1
5. คืน unhappy

การนำไปใช้งาน (Python)

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, None):
                unhappy += 1
                break
        for pref in graph[end]:
            if graph[pref].get(end, None):
                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))

อินพุต

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

เอาต์พุต

2