ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1557. Network Attack

1557. Network attack
Послано mahbubul 23 сен 2007 16:57
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
Послано N.M.Hieu ( DHSP ) 6 окт 2007 02:09
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
Послано caoqinxiang 21 ноя 2007 16:57
i make a perfect algorithm of O(m+n)to find 2-cuts
Re: 1557. Network attack
Послано marqueewinq [Troizk] 5 фев 2012 15:41
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