Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

Alternate solution to 1325F:Ehab's Last Theorem

Revision en1, by HealthyUG, 2020-03-15 15:11:06

There's another simple greedy solution to the problem using dfs trees.

First form a dfs tree of the graph with any vertex as its root. Now consider a vertex $$$P$$$ which has a backedge to vertex $$$Q$$$, if $$$depth(P)-depth(Q)+1 >= \lceil\sqrt{n}\rceil$$$ then we have found a cycle of at least $$$\lceil\sqrt{n}\rceil$$$ vertices.

If we cannot find such a cycle, we'll find an independent set, we know that the leaves of a dfs tree do not have an edge between them. So we'll take all the leaves in the independent set. But that may not be enough we need more vertices, so we'll choose each such vertex whose depth is at least $$$\left(\lceil\sqrt{n}\rceil - 1\right)$$$ less than the minimum depth of all the chosen vertices in it's subtree and insert it to the independent set (we can do so because if there is an edge between the current vertex and any of the previously chosen vertices, we would have found a cycle). How can we say that such an independent set will have at least $$$\lceil\sqrt{n}\rceil$$$ vertices? Here is an intuitive proof:-

Consider any linear chain in the dfs tree of length $$$L$$$ which terminates at a single leaf, we can pick $$$\lceil\frac{L}{\sqrt{n}}\rceil$$$ vertices from this chain. Whenever we put a vertex in the independent set, we can disconnect its entire subtree from the graph and consider it as a new leaf. After this we can select any other linear chain and repeat this process.

In total, we'll have $$$\sum{\lceil\frac{L}{\sqrt{n}}\rceil}$$$ vertices in our independent set which is at least $$$\lceil\frac{n}{\sqrt{n}}\rceil = \lceil\sqrt{n}\rceil$$$ (since $$$\sum{L} = n$$$).

I'd appreciate if someone can come up with a more concrete proof.

Here is my accepted solution: https://codeforces.com/contest/1325/submission/73328247

Tags #dfs and similar, #tutorial, #graphs

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English HealthyUG 2020-03-15 15:11:06 1805 Initial revision (published)