Please read the new rule regarding the restriction on the use of AI tools. ×

IMstuNNing's blog

By IMstuNNing, history, 23 months ago, In English
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorial is at https://codeforces.me/blog/entry/106675 — Understanding it will give clues to how to solve with DSU.

A hint for DSU: Consider the strategy of building the graph. Do we have to build the whole graph to find the solution? No, and in fact we cannot — that would take O(n^2) time and be too slow. What could we build instead of the graph?