I am getting WA in second case i dont know why.

my idea is: first find out the number of articulation bridge in the graph say n. then ans1 = nC2 + n*(E-n).

then, we need to merge all the multiple edge and again find out all the biconnected component. there after:

ans2 = number of nodes having degree 2 within its own component.

ans3 = number of nodes having degree (multiple edge) 2 with one another component.

then ans = asn1 + ans2 + ans3/2.

I cant understand where does my code fail? can any one help?

Try this test :
6 10
1 2
1 2
2 3
1 3
4 5
5 6
4 6
4 6
2 4
3 5

The answer is 1 : (2,4) and (3,5)

Edited by author 06.10.2007 02:10

We must use standard theory as possible.
I think problems divided to two parts:
1. Find all bridges- well known,O(n+m) algorithms;
2. Find all 2-cuts - I don't know algoriths and
best complexity.
I think It is must be something as 3-connected blocs structure.



Edited by author 07.11.2007 12:40

i make a perfect algorithm of O(m+n)to find 2-cuts

I've solved this problem, but i'm intrested in a different ways to compute 2-cuts. Could you send me your code?
marqueewinq@gmail.com