mujtaba1747's blog

Need help for Counting components of the complement of a graph. (Problem : 0-1 MST)
By mujtaba1747, history, 5 years ago, In English

I came across this problem : 1242B - 0-1 MST It requires us to find components of the complement of the graph. The editorial asks us to use DSU (Disjoint set union) to find the components but I'm not able to understand how to proceed after initializing the DSU.

Any suggestion / comment is greatly appreciated.

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problem is the same as 190E - Counter Attack and 920E - Connected Components?, if you want to look at more solutions. I have to imagine most people used a BFS to solve it than DSU. Amusingly, I used a BFS when solving 920E, but a DSU when solving 1242B.

920E BFS solution: https://codeforces.net/contest/920/submission/34879429 1242B DSU solution: https://codeforces.net/contest/1242/submission/64392337.

The core idea for my DSU solution is to consider the adjacency list of the graph. Say node $$$u$$$ is connected to vertices $$$v_1, v_2, \ldots, v_k$$$ which are in sorted order ($$$v_1 < v_2 < \ldots < v_k$$$). Then we need to merge vertex $$$u$$$ with the ranges $$$[0, v_1 - 1]$$$, $$$[v_1 + 1, v_2 - 1]$$$, and so on. To do this efficiently, we can merge those ranges by keeping track of the largest range starting at each index, and then merging $$$u$$$ with the start of each range. This runs in $$$O(m \alpha(n))$$$.

→ Reply