Sammmmmmm's blog

Count no. of connected components in N * N matrix (N <= 1e9)
By Sammmmmmm, history, 10 months ago, In English

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!

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it -41 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

→ Reply