What is the best implementation of finding 2CCs in a graph and compressing it into a tree?
This is what I currently use:
// include some implementation of dsu data structure
void dfs(int u, int p = -1)
{
tin[u] = low[u] = ++timer;
for (int v : g[u])
if (v != p)
{
if (tin[v])
low[u] = min(low[u], tin[v]);
else
{
dfs(v, u);
low[u] = min(low[u], low[v]);
// if u and v are in the same 2CC
if (low[v] <= tin[u])
unite(u, v);
}
}
}
void compress_graph()
{
for (int u = 0; u < n; u++)
for (int v : g[u])
if (find(u) != find(v))
G[find(u)].push_back(find(v));
}
Here, $$$g$$$ is the original graph's adjacency list and $$$G$$$ is the compressed 2CC-graph's adjacency list.