brdy's blog

By brdy, history, 12 months ago, In English,

For SCCs if we want to answer the query "are A and B in the same component?" it's quite easy because each vertex belongs to only one component. We can store color[i] and compare them.

But this idea won't work for biconnected components. Cut vertices (articulation points) can be part of O(N) BCCs. I'm not sure if there is a solution for the general case of "are A and B in the same BCC?". Can we do some processing to solve this problem for biconnected components in sublinear time?

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

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

yo so you know the block cut tree? in a block cut tree, every vertex represents either a BCC or a cut vertex -- you connect a cut vertex to a BCC only if that cut vertex is in that BCC. so i think if you root this tree, cut vertices are in the same BCC only if both are either the children/ancestor of the same BCC