1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64  // @Title: 重构一棵树的方案数 (Number Of Ways To Reconstruct A Tree) // @Author: 15816537946@163.com // @Date: 2022-02-16 00:30:41 // @Runtime: 400 ms // @Memory: 27.6 MB func checkWays(pairs [][]int) int { adj := map[int]map[int]bool{} for _, p := range pairs { x, y := p[0], p[1] if adj[x] == nil { adj[x] = map[int]bool{} } adj[x][y] = true if adj[y] == nil { adj[y] = map[int]bool{} } adj[y][x] = true } // 检测是否存在根节点 root := -1 for node, neighbours := range adj { if len(neighbours) == len(adj)-1 { root = node break } } if root == -1 { return 0 } ans := 1 for node, neighbours := range adj { if node == root { continue } currDegree := len(neighbours) parent := -1 parentDegree := math.MaxInt32 // 根据 degree 的大小找到 node 的父节点 parent for neighbour := range neighbours { if len(adj[neighbour]) < parentDegree && len(adj[neighbour]) >= currDegree { parent = neighbour parentDegree = len(adj[neighbour]) } } if parent == -1 { return 0 } // 检测 neighbours 是否为 adj[parent] 的子集 for neighbour := range neighbours { if neighbour != parent && !adj[parent][neighbour] { return 0 } } if parentDegree == currDegree { ans = 2 } } return ans }