Question about Biconnected Components

Revision en1, by brdy, 2018-11-22 06:17:20

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?

Tags bccc, tarjan, oleg, bitset


  Rev. Lang. By When Δ Comment
en1 English brdy 2018-11-22 06:17:20 525 Initial revision (published)