bridge / critical links

[asif_rahman0]

Undirected graph. ok.
"Critical link is an egde whose removal disconnects a graph(G)."

1->2
1->4
4->3
2->5
3->2
3->10
3->9
5->6
5->7
7->8
5->8
8->2
2->7

here is a graph of 13 edges.
now my question is how many bridge or critical links is here?
i think here is only --->
3-10
3-9
5-6
Am i right?

but here is a problem about vertex 2. It is an articulation point but not critical link?? may be i m missing something!!!

plz help.

[misof]

You are right.

An equivalent definition: edge is a bridge if and only if it is not a part of any cycle. In your graph, the edges 3-9, 3-10, and 5-6 are bridges.

A vertex is an articulation point (somewhere you can see also the name "cutvertex") if and only if its removal increases the number of components.

In your graph, articulation points are the vertices 2, 3, and 5.

[asif_rahman0]

Thnx misof. Just learned the name of CutVertex from you:). Before i dont know it.

Now i am confident about it. And also i coded 796(critical links).
But getting WA.

Could you send me some input output in PM or here?

please help.

[Moheeb]

Asif wrote:
Thnx misof. Just learned the name of CutVertex from you:). Before i dont know it.

Really ? u shouldn't go too far to know about it, look at Rosen's Discrete book,
section 8.4 , example 7 . BTW, this problem is really easy.