Reputation: 31
I have a graph and I have identified all of its biconnected components and all of its critical vertexes/articulation points using Tarjan's Algorithm.
I am trying to create a new graph using the biconnected components: the components will be the new vertices and two biconnected components are linked if they share at least one articulation point.
For example, for the graph in the image below, the adjacency lists for the new graph would be:
(1, 3) -> (3, 4, 5), (1, 2)
(1, 2) -> (1, 3)
(3, 4, 5) -> (1, 3)
where (1, 3), (1, 2), (3, 4, 5) are the biconnected components and 1, 3 are articulation points. How could I create the new graph/the adjacency lists in a relatively optimal way? Can I do it while I'm running Tarjan on the graph?
Edit: A biconnected component is a subset of the vertices of the graph where every vertex in this subset will remain connected even if you remove any vertex of the graph. Wiki page for biconnected component
Upvotes: 2
Views: 197
Reputation: 2777
Yes you can do it quite easily using DSU(Disjoint Set Union, aka Union Find) data structure.
The key is noticing some observations:
Now we can already do some tarjan modifications:
(u,v)
if it's a bridge save it for later useu
and v
belong toUpvotes: 1