1719. Number Of Ways To Reconstruct A Tree Hard

1/**
2 * [1719] Number Of Ways To Reconstruct A Tree
3 *
4 * You are given an array pairs, where pairs[i] = [xi, yi], and:
5 * 
6 * 	There are no duplicates.
7 * 	xi < yi
8 * 
9 * Let ways be the number of rooted trees that satisfy the following conditions:
10 * 
11 * 	The tree consists of nodes whose values appeared in pairs.
12 * 	A pair [xi, yi] exists in pairs if and only if xi is an ancestor of yi or yi is an ancestor of xi.
13 * 	Note: the tree does not have to be a binary tree.
14 * 
15 * Two ways are considered to be different if there is at least one node that has different parents in both ways.
16 * Return:
17 * 
18 * 	0 if ways == 0
19 * 	1 if ways == 1
20 * 	2 if ways > 1
21 * 
22 * A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
23 * An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.
24 *  
25 * Example 1:
26 * <img src="https://assets.leetcode.com/uploads/2020/12/03/trees2.png" style="width: 208px; height: 221px;" />
27 * Input: pairs = [[1,2],[2,3]]
28 * Output: 1
29 * Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
30 * 
31 * Example 2:
32 * <img alt="" src="https://assets.leetcode.com/uploads/2020/12/03/tree.png" style="width: 234px; height: 241px;" />
33 * Input: pairs = [[1,2],[2,3],[1,3]]
34 * Output: 2
35 * Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
36 * 
37 * Example 3:
38 * 
39 * Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
40 * Output: 0
41 * Explanation: There are no valid rooted trees.
42 *  
43 * Constraints:
44 * 
45 * 	1 <= pairs.length <= 10^5
46 * 	1 <= xi < yi <= 500
47 * 	The elements in pairs are unique.
48 * 
49 */
50pub struct Solution {}
51
52// problem: https://leetcode.com/problems/number-of-ways-to-reconstruct-a-tree/
53// discuss: https://leetcode.com/problems/number-of-ways-to-reconstruct-a-tree/discuss/?currentPage=1&orderBy=most_votes&query=
54
55// submission codes start here
56
57impl Solution {
58    pub fn check_ways(pairs: Vec<Vec<i32>>) -> i32 {
59        0
60    }
61}
62
63// submission codes end
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn test_1719() {
71    }
72}
73