Question about Biconnected Components

Правка en1, от 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?

Теги bccc, tarjan, oleg, bitset

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский brdy 2018-11-22 06:17:20 525 Initial revision (published)