Graph Representation through Adjacency List.
In a given chordal graph, Jerry can start from any vertex and move to any neighbouring vertex throughout the chase. You have to find the minimum number of cats Tom needs, to corner Jerry after a finite number of rounds. Tom can, however, choose any set of vertices, independent of the chosen vertices in the previous rounds.
Let us assume, the minimum number of cats required to be K. To find K, we can start somewhat in a greedy way. The minimum value of K can be 2. So, we can erase all vertices having degree 1 (because if Jerry lands upon any of these vertices, he is sure to get cornered). If there still exists some vertices, we can conclude, that 2 cats are not enough to catch Jerry. So, we increase K to 3 and repeat the same procedure.
For Subtask #1 and #2:
Proceed in the exact same way, as explained in “QUICK EXPLANATION”.
Click to view
- Arrange all the vertices in increasing order of their degree.
- Remove all the vertices having the lowest degree, along with their edges.
- If there are still any vertex left, go to Step 1.
- ‘K’ is 1 + degree of the last removed vertex.
For Subtask #3:
The most expensive step in the previous algorithm which results in TLE verdict is the step where the list of vertices is sorted. Also, the vertex removal step is quite expensive if done on an ‘ArrayList’ or ‘vector’.
We can improve this by using a ‘HashSet’ or a hash function to design the adjacency list, so that any insertion or deletion can be carried out in O(1) time complexity.
Furthermore, we can improve the ‘sorting’ step by maintaining a ‘TreeSet’, or a ‘PriorityQueue’ (Binary Heap) for lg(N) insertion and deletion. However, the heap needs to be updated after each deletion of the vertices.
This problem is also equivalent to finding the maximum chordal clique in the graph. For this implementation you can have a look at this solution.
This is my first editorial. Please do comment, and point out any error you find.