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.net/contest/1325/submission/73328247