### P_Nyagolov's blog

By P_Nyagolov, 9 years ago,

UPD: I cannot fully understand Xellos' solution but a friend of mine(radoslav11) wrote this code and got AC with it. The bad thing is that neither me nor him can prove the correctness of the algorithm. At least for me this seems not to be right:

 if(v != parent[u])
low[u] = min(low[u], low[v]);


Can anybody prove the correctness of the code or give a counter example and if such example exists can you explain in details another algorithm that is correct, please? :)

Hello everybody,

Recently, I started learning about articulation points, bridges, bi-connected components and strongly connected components. I decided to solve some problems from lightoj and I can't solve this one.

In short, you are given an undirected connected graph with N vertices and M edges (N<=10000, M<=20000). Find the minimum edges we need to add so that the graph should not contain a bridge.

Can anybody tell me what the solution is and prove its correctness since I came up with some algorithms that seemed correct to me but after a while I found some counter-examples, please? And can you give me some problems to solve involving those topics because now the seem kinda confusing to me and I think that I need to practice more, please?

Another question that I want to ask is: I know that a bi-connected graph is a graph without articulation points. But is it true that if a graph doesn't contain a bridge, then it is bi-connected and is it true that if a graph is bi-connected, then it contains a bridge and why?