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
}
|