Блог пользователя Sammmmmmm

Count no. of connected components in N * N matrix (N <= 1e9)
Автор Sammmmmmm, история, 16 месяцев назад, По-английски

Given an N * N matrix consisting of k ones and the rest are 0s.Count the number of connected components that contains only zeros

N <= 1e9

K <= 1e5

Thanks!

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Sammmmmmm (previous revision, new revision, compare).

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

As far as i understand this graph will be always connected)

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

If you have consecutive columns filled only with zeros, you can compress them into one column (which doesn't change reachability). After that, group the zeros into maximal vertical segments. The graph constructed by adding edges between segments that are adjacent to each other has the same number of components as our original graph. We can construct it "brutally" with some sort of sweep-line, because it is planar and therefore sparse.

→ Ответить