|
|
вернуться в форум1557. Network attack 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? Re: 1557. Network attack 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 Re: 1557. Network attack Послано svr 7 ноя 2007 12:24 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 Re: 1557. Network attack i make a perfect algorithm of O(m+n)to find 2-cuts Re: 1557. Network attack 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 |
|
|