题目描述思路
构造树并验证树的合法性
Python实现Java实现
题目描述
重构一棵树的方案数
思路 构造树并验证树的合法性
首先是题目关于方案数条件的描述中第二条，当且仅当表示的是所有在pairs中的数对都具有祖先孙子关系，并且所有具有祖孙关系的结点都是pairs中的数对。
假设树中的结点数目为n，pairs中包含结点x的数对数目为degree[x]，结点x的祖先和后代结点集合为adj[x]。
首先，根结点为树中其余所有结点的祖先，根结点与其余所有结点都能构成数对，假定根结点为root，则degree[root]=n-1。其次，对于pairs中的数对[xi, yi]，如果xi为yi的祖先，则一定满足degree[xi] >= degree[yi]。如果yj是yi的后代节点，则yj一定也是xi的后代节点；如果yj是yi的祖先结点，则yj要么是xi的祖先节点，要么是后代节点；不管是哪种情况，一定满足degree[xi] >= degree[yj]。如果xi是yi的祖先，则adj[yi]∈adj[xi]。
另外，对于pairs中的数对[xi, yi]，如果xi是yi的祖先，且满足degree[xi] = degree[yi]和adj[xi] = adj[yi]，则xi到yi的途径的所有节点均只有一个孩子节点。此时xi到yi之间的节点包含的数对关系是一样的，xi到yi的节点可以互相交换位置而不影响树的结构，则此时构成树的方案数必不唯一。
所以对于pairs中的数对[xi, yi]有以下结论：
如果degree[xi] > degree[yi]，则xi为yi的祖先节点；如果degree[yi] > degree[xi]，则yi为xi的祖先节点；如果degree[xi] = degree[yi]，则可能存在多种构造方法，yi为xi的祖先或xi为yi的祖先。
通过以上分析结论，构造树，并检查树是否合法。
首先找到根节点root，找到满足degree[root] = n-1的节点，如果不存在根节点，则认为其不能构成合法的树，返回0。利用上述的结论检测构建的树是否合法，遍历每个节点nodei，找到其祖先parenti，检测adj[nodei]是否为adj[parenti]的子集。利用degree[nodei] <= degree[parenti]找到所有属于nodei的祖先节点，然后依次检测是否满足adj[nodei] ∈adj[parenti]，如果不满足要求，则构建的数非法，返回0。实际检测过程中不比检测节点nodei的所有祖先节点，只要检测节点nodei的父结点是否满足子集包含的要求即可。根据上述结论，找到节点x满足degree[x]最小且degree[x] >= degree[nodei]，则此时找到的节点为节点nodei的父亲节点，此时只需检测父亲节点是否满足上述要求即可。设nodei的父结点为parent，若满足degree[nodei] = degree[parent]，则树的构造方式有多个，返回2。 Python实现
class Solution:
def checkWays(self, pairs: List[List[int]]) -> int:
adj = defaultdict(set)
for x, y in pairs:
adj[x].add(y)
adj[y].add(x)
root = next((node for node, neighbours in adj.items() if len(neighbours) == len(adj) - 1), -1)
if root == -1:
return 0
ans = 1
for node, neighbours in adj.items():
if node == root:
continue
curDegree = len(neighbours)
parent = -1
parentDegree = maxsize
for neighbour in neighbours:
if curDegree <= len(adj[neighbour]) < parentDegree:
parent = neighbour
parentDegree = len(adj[neighbour])
if parent == -1 or any(neighbour != parent and neighbour not in adj[parent] for neighbour in neighbours):
return 0
if curDegree == parentDegree:
ans = 2
return ans
Java实现
class Solution {
public int checkWays(int[][] pairs) {
Map> adj = new HashMap>();
for (int[] p : pairs) {
adj.putIfAbsent(p[0], new HashSet());
adj.putIfAbsent(p[1], new HashSet());
adj.get(p[0]).add(p[1]);
adj.get(p[1]).add(p[0]);
}
int root = -1;
Set>> entries = adj.entrySet();
for (Map.Entry> entry : entries) {
int node = entry.getKey();
Set neighbours = entry.getValue();
if (neighbours.size() == adj.size() - 1) {
root = node;
}
}
if (root == -1) {
return 0;
}
int res = 1;
for (Map.Entry> entry : entries) {
int node = entry.getKey();
Set neighbours = entry.getValue();
if (node == root) {
continue;
}
int currDegree = neighbours.size();
int parent = -1;
int parentDegree = Integer.MAX_VALUE;
for (int neighbour : neighbours) {
if (adj.get(neighbour).size() < parentDegree && adj.get(neighbour).size() >= currDegree) {
parent = neighbour;
parentDegree = adj.get(neighbour).size();
}
}
if (parent == -1) {
return 0;
}
for (int neighbour : neighbours) {
if (neighbour == parent) {
continue;
}
if (!adj.get(parent).contains(neighbour)) {
return 0;
}
}
if (parentDegree == currDegree) {
res = 2;
}
}
return res;
}
}
