用 Python 计算不开心的朋友数量的程序
假设我们有n(even)不同朋友的偏好列表。对于每个人i，preferences[i]包含一个按偏好顺序排序的朋友列表。因此，列表中较早的朋友比列表中较晚的朋友更受欢迎。每个列表中的朋友都按从0到n-1的整数编号。所有的朋友被分成不同的对。其中pairs[i]=[xi,yi]表示xi与yi配对和/或yi与xi配对。但是，如果x与y配对并且存在一个也与v配对的朋友u，则朋友x不高兴，但是-
x比y更喜欢u，并且
你更喜欢x而不是v。
我们必须找到不开心的朋友的数量。
因此，如果输入类似于首选项=[[1,2,3],[3,2,0],[3,1,0],[1,2,0]]对=[[0,1],[2,3]]，那么输出将是2因为第一个朋友不开心，因为人1与人0配对但更喜欢人3而不是人0，人3更喜欢人1而不是人2。朋友3不快乐因为第3个人与第2个人配对，但更喜欢第1个人而不是第2个人，第1个人更喜欢第3个人而不是第0个人。
示例
让我们看看以下实现以获得更好的理解-
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