leetcode:抽象模拟重构一棵树的方案数

直接看算法吧&＃xff1a;

src:

class Solution:def checkWays(self, pairs: List[List[int]]) -> int:# 又来搞心态呗# print(maxsize)# 抽象分析...一脸懵逼...# 根度数n - 1# 找到比当前node大但最接近的parent# 检测是否满足自己# 若度数相等就多种构造# 否则一种# 找出所有的邻居adj &＃61; defaultdict(set)for x, y in pairs:adj[x].add(y)adj[y].add(x)# 检测是否存在根节点# next函数的使用root &＃61; next((node for node, neighbours in adj.items() if len(neighbours) &＃61;&＃61; len(adj) - 1), -1)if root &＃61;&＃61; -1:return 0ans &＃61; 1for node, neighbours in adj.items():# 不用再判断root了if node &＃61;&＃61; root:continuecurDegree &＃61; len(neighbours)parent &＃61; -1parentDegree &＃61; maxsize# 根据degree的大小找到的node的父节点&＃xff08;离他最近但大于等于它的&＃xff09;for neighbour in neighbours:if curDegree <&＃61; len(adj[neighbour]) < parentDegree:parent &＃61; neighbourparentDegree &＃61; len(adj[neighbour])# 检测neighbours是否为adj[parent]的子集if parent &＃61;&＃61; -1 or any(neighbour !&＃61; parent and neighbour not in adj[parent] for neighbour in neighbours):return 0# 相等的话多种构造if parentDegree &＃61;&＃61; curDegree:ans &＃61; 2return ans


总结&＃xff1a;
直接模拟
用next取iter中的元素&＃xff0c;越超界则返回给定值