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
}