My solution to “Chef and College”, from the July 2018 LoC Contest, is getting TLE in one testcase of the second subtask: https://www.codechef.com/viewsolution/19359475 . I tried using a simple union-find approach, and would like to know how the algorithm could be optimized. Thanks.
Use DSU data structure to solve ,your code is giving tle just because you run a O(N) loop to make them friend,where it can be done with DSU with very less constant time complexity.
link of DSU : https://www.hackerearth.com/practice/notes/disjoint-set-union-union-find/
link to my soln : https://www.codechef.com/viewsolution/19357712
Thank you, that was very helpful.
welcome 