Hello Everyone,
Can anyone help me regarding this problem from acm icpc 2019? I was applying simple dfs to construct the tree but I got WA and I also realize that it is not so simple. May be I am not able to understand the problem.
According to me,the only time when the tree cannot be constructed is when the graph is disconnected.Are there any other conditions??I think that a connected graph will always give us a tree by applying dfs and dfs will hold the edge relation in the given graph.
Thanks in advance to anyone who would help me…
Answer
Let us assume there exist such a tree. Also add the node itself to the adjacency list.
Observation 1
Now we can see that that the root node is a an ancestor of all the nodes. Therefore we can deduce it must have n edges.
Observation 2
Each path from the root to a leaf will be fully connected(Every pair of nodes will have an edge).
Observation 3
We cannot differentiate between the nodes that have n edges, since they are all connected to everything else, so any of them may be the root and we will get a correct answer.
Observation 4
The number of edges is the number of the nodes in it’s subtree plus the number of ancestors as these are the only ones that satisfy the given conditions.
Observation 5
Each node will be connected to at least one node with at least as many edges as itself except the root node since the ancestor’s subtree will be larger by at least one, and the number of ancestors of the immediate ancestor will be less by only one.
Observation 6
Therefore we can build the tree by going in decreasing order of the edge sizes, since every node’s parent will already be in the tree.
Observation 7
Notice that in any subgraph that is a line, all of the nodes will have the same adjacency list, since they will still be in the same paths, therefore we can swap them to still get an answer(Observation 2).
Observation 8
The order won’t be fixed because some nodes may have equal number of edges. Any such order will be correct. This can be proved by the fact the number of edges is the sum of ancestors plus the size of the subtree. For the number of edges to be equal there are 2 cases. They either have an edge between them or they don’t.
If they don’t have an edge, any order is fine, because it won’t be the child of any node in it’s subtree.
If they do, we can claim that all the nodes in the path have only have one child(Use observation 4) Therefore swapping two of them will still create the same graph(Observation 7).
Observation 9
Now we know that we can go in decreasing size of adjacency list, we still need to find which node is the parent. Check all the nodes it’s connected to in the current tree, and connect it to the deepest one, since all of the other nodes in it’s adjacency list must be ancestors of that node. Remember we assumed a tree exists.
Final Algorithm
Sort the nodes in decreasing order of the size of the adjacency list. Then make the first node the root, and then keep on adding edges to the deepest node it’s connected to in the current tree. This will create a correct tree if there exist a solution. Now check if this tree satisfies the answer. If it doesn’t, there doesn’t exist any tree.
My solution : CodeChef: Practical coding for everyone
2 Likes
Thank you Sir for your quick response.I am reading your answer and trying to understand.In the meantime, it will be helpful to know why a simple dfs of the given graph does not work?