3
$\begingroup$

There are a set $A$ of trees. There is another set $B$ of trees that is the collection of all possible subtrees of the trees in $A$. I don't have $A$ but only have $B$, and I need to figure out the size of $A$. A brute-force way is making a graph of the trees. For each root node in $B$, find a tree that contains the node, if there exists such a tree, then make a link from the root node's tree to the containing tree. Finally I can obtain the number of trees in $A$ by counting the number of connected components in the graph. However, this may not be so efficient. How can I do it efficiently?

$\endgroup$
1
$\begingroup$

You can't do it at all, let alone do it efficiently. Consider a tree $T$ and let its set of subtrees be $S$. If you're told $B=S$, the cardinality could be anything between $1$ and $|S|$, inclusive, because $A$ could be any subset of $S$ that contains $T$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Maybe he meant that B is a multiset? $\endgroup$ – Pavel Oct 17 '15 at 3:41
1
$\begingroup$

In addition to David's answer I wanna say that, if B was a multiset (meaning you can store several trees that are the same in that set) then you could do it by taking the biggest size tree in B and generating all it's subtrees and removing them from B, then taking the next biggest subtree in B (out of what's left) and doing the same thing until your multiset is empty.

All that can be efficiently achieved with a priority queue.

It's similar to this problem: codeforces.com/problemset/problem/582/A?locale=en .

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.