You are given an array pairs
, where pairs[i] = [xi, yi]
, and:
- There are no duplicates.
xi < yi
Let ways
be the number of rooted trees that satisfy the following conditions:
- The tree consists of nodes whose values appeared in
pairs
. - A pair
[xi, yi]
exists inpairs
if and only ifxi
is an ancestor ofyi
oryi
is an ancestor ofxi
. - Note: the tree does not have to be a binary tree.
Two ways are considered to be different if there is at least one node that has different parents in both ways.
Return:
0
ifways == 0
1
ifways == 1
2
ifways > 1
A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
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.
Example 1:
Input: pairs = [[1,2],[2,3]] Output: 1 Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
Example 2:
Input: pairs = [[1,2],[2,3],[1,3]] Output: 2 Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
Example 3:
Input: pairs = [[1,2],[2,3],[2,4],[1,5]] Output: 0 Explanation: There are no valid rooted trees.
Constraints:
1 <= pairs.length <= 105
1 <= xi < yi <= 500
- The elements in
pairs
are unique.
Solution: Bitset
Time complexity: O(E*V)
Space complexity: O(V^2)
C++
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 |
// Author: Huahua class Solution { public: int checkWays(vector<vector<int>>& pairs) { // Construct a map, key is the node, value is the accessible nodes. unordered_map<int, bitset<501>> m; for (auto& e : pairs) m[e[0]][e[0]] = m[e[1]][e[1]] = m[e[0]][e[1]] = m[e[1]][e[0]] = 1; // The tree must have one+ node/root that has paths to all the nodes. if (!any_of(begin(m), end(m), [&m](const auto& kv) { return kv.second.count() == m.size();})) return 0; int multiple = 0; for (const auto& e : pairs) { // For each pair, check whether one can be the parent of another // that can conver all the children nodes. const auto& all = m[e[0]] | m[e[1]]; const int r0 = m[e[0]] == all; const int r1 = m[e[1]] == all; if (r0 + r1 == 0) return 0; // If both can be parents, there can be multiple trees. multiple |= r0 * r1; } return 1 + multiple; } }; |
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
# Author: Huahua class Solution: def checkWays(self, pairs: List[List[int]]) -> int: m = defaultdict(set) for u, v in pairs: m[u] |= set((u, v)) m[v] |= set((u, v)) if not any(len(m[x]) == len(m) for x in m): return 0 multiple = 0 for u, v in pairs: union = m[u] | m[v] ru, rv = int(m[u] == union), int(m[v] == union) if not ru + rv: return 0 multiple |= ru * rv return 1 + multiple |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment