Ehab’s Last Corollary

Source: Codeforces 1364D

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.

In the problem statement, it is claimed that one of the two properties always holds. This doesn’t seem obvious!

2. Consider why at least one of the two properties must hold in any graph with at least k vertices.
   • What properties might lead to the first being true?
   • What properties might lead to the second being true?
   • You aren’t expected to find a proof in this part; just build some intuition.

Let’s narrow the scope of our search.

3. Prove that if the claim in the question is true, then we can always find a suitable cycle or independent set among only the first k vertices of the graph.

4. Design an algorithm to determine whether there is a cycle among the first k vertices.
   • If so, find the vertices of such a cycle, in order.
   • If not, what property does this portion of the graph have? How can you identify independent subsets, and group them together if necessary?

5. Analyse the time complexity of your algorithm and estimate its running time.

6. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
7. Submit your program for judging!
   • Debug as required.