首页 > 网易9.12算法笔试第四题暴力法
头像
Glooory
编辑于 2020-09-12 17:50
+ 关注

网易9.12算法笔试第四题暴力法

第四题 找对象
import sys
boys = [int(i) for i in sys.stdin.readline().strip().split(' ')]
girls = [int(i) for i in sys.stdin.readline().strip().split(' ')]
n = int(sys.stdin.readline().strip())
from collections import defaultdict

degree = defaultdict(int)
neighbors = defaultdict(list)
all = []

for i in range(n):
    line = sys.stdin.readline().strip().split(' ')
    a = int(line[0])
    b = int(line[1])
    degree[a] += 1
    degree[b] += 1
    neighbors[a].append(b)
    neighbors[b].append(a)
    all.append(a)
    all.append(b)

all.sort()
all_without_repeat = []
for i in range(len(all)):
    if i != 0 and all[i-1] == all[i]:
        continue
    all_without_repeat.append(all[i])
all_without_repeat.sort(key=lambda x:degree[x])
for value in neighbors.values():
    value.sort(key=lambda x:degree[x])

count = 0
while len(all_without_repeat) != 0:
    t = all_without_repeat.pop(0)
    for i in neighbors[t]:
        degree[i] -= 1
    if len(neighbors[t]) != 0:
        cur = 0
        while cur < len(neighbors[t]):
            neigh = neighbors[t][cur]
            try:
                all_without_repeat.remove(neigh)
                for i in neighbors[neigh]:
                    degree[i] -= 1
                count += 1
                break
            except:
                cur += 1
    all_without_repeat.sort(key=lambda x: degree[x])
    for value in neighbors.values():
        value.sort(key=lambda x: degree[x])
print(count)


全部评论

(0) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐