Hummus_'s blog

By Hummus_, history, 7 weeks ago, In English

I was solving this problem and i am struggling to find why my code gives WA

Problem: https://codeforces.com/contest/1609/problem/D

Code: https://ideone.com/wAdd28

My approach:

When I take u,v I first make sure if it will help connect 2 components together or not

if it will help then I add it to the edges vector and if not then this i can be used to connect 2 components that don't have u and v and the answer will be true so I increment variable x.

after that, I reset the prt array and then perform dsu but only on the edges contained in the edges vector.

after that, I loop from 0 to x to connect the biggest 2 components every time, and after that, I loop over prt array and find the component with the max size and that's my answer

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it