TLE in only one test case of COLCHEF

My solution to “Chef and College”, from the July 2018 LoC Contest, is getting TLE in one testcase of the second subtask: CodeChef: Practical coding for everyone . 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 : Disjoint Set Union (Union Find) | HackerEarth

link to my soln : CodeChef: Practical coding for everyone

1 Like

Thank you, that was very helpful.

welcome :slight_smile: