CommonLounge Archive

[659E] New Reform (Graph Problem)

December 24, 2016

In this question, if it is modeled as a tree then yes, there is only 1 separate city, that’s intuitive, but there can be several cycles, here is where I am stumped.

I could consider a vertex to be a starting point and perform dfs but there are 10^5 vertices, so no. I didn’t really understand the editorial either.

Hints please?

© 2016-2022. All rights reserved.