LeetCode 1192. Critical Connections in a Network Explanation and Solution

Thanks in advance. :D

Happy coding every day!

[anant]

Thanks for the explanation. Is yours modified Tarjan's algo?
(sv = start vtx, cv = cur vtx, av = adj vtx) The one I have seen updates cv's low link with dis time of av only if av has already been visited while visiting all av's of cv. And if av is parent, does not do anything.

Here is that code (Tarjan'a algo for finding bridges and articulation points):
private void dfs_updt_cv_lowlink(int startVtx, int cv, int parent, List<List<Integer>> li_bridges)
{
// if sv became parent of cv, then there is an out edge from sv to cv (sv --> cv)
if (startVtx == parent) startVtx_cOutEdges++;

// process cv
// for cv, mark as visited and update its discovery time (ID the vtx)
visited[cv] = true;
lowlink[cv] = disTime[cv] = m_next_disTime++;

// process neighbors of cv, and update lowlink for cv
for (int av : aAL[cv])
{
// pv --> cv --> av
// since it is an undirected graph,
// there is an edge back to parent (from cv), ignore this edge
if (av == parent) continue; // back edge

if ( ! visited[av])
{
// update lowlink for av
dfs_updt_cv_lowlink(startVtx, /*curr*/ av, /*parent*/ cv, li_bridges);


// update lowlink for cv on dfs(av) callback
// since cv can reach av, cv can reach any lowlink of av
lowlink[cv] = Math.min(lowlink[cv], lowlink[av]);

if (disTime[cv] < lowlink[av]) // .LT.
{
List<Integer> bridge = new ArrayList<>();
bridge.add(cv);
bridge.add(av);

li_bridges.add(bridge);
}

if (disTime[cv] <= lowlink[av]) // .LE. (LT = via bridge, LE = via cycle)
isArPt[cv] = true;
}
else
{
// from cv, we are visiting av
// if av already visited and has low dis time, update cv's lowlink
// think of disTime as ID -- if u can visit a lower ID, update your lowlink
lowlink[cv] = Math.min(lowlink[cv], disTime[av]);
}
} // end for (int av : aAL[cv])
}

And then we have the outer loop to dfs all unvisited vtx

// Iter thru all unvisited vtx (consider such vtx as start vtx)
// we use the term startVtx instead of cv, since in dfs, as we trav, we have cv, parent vtx, etc.
for (int startVtx = 0; startVtx < V; ++startVtx)
{
if (visited[startVtx]) continue;

// trav all vtx in CC of startVtx, starting from startVtx
startVtx_cOutEdges = 0;
int cv = startVtx;
dfs_updt_cv_lowlink(startVtx, /*cur*/ cv, /*parent*/ UNKNOWN_PARENT, li_bridges);

isArPt[startVtx] = (startVtx_cOutEdges > 1);
}

return li_bridges;

[chodingninjas]

I WAS SEARCHING THIS SOLUTION EVERYWHERE THNX

[jiechaowang]

Thanks for this video. A little bit advice, you could benefit a lot working more on your presentation and language skills :)