Тема: графы?да, графы?
Дан орграф.Нужно найти вершину сток и вершину исток в нём.Ограничения большие, то есть нужно уложиться в 1-2 обхода.
P.S мне кажется что здесь конденсация 
Re: графы?да, графы?
уверен, что ничего не забыл сообщить из условия?
если "исток" есть, то он будет единственной вершиной с нулевой степенью входа, для "стока" аналогично. вообще, каково формальное их определение в задаче?
Re: графы?да, графы?
Исток-из него достижимы все вершины.(необязательно напрямую)
Сток-он достижим из всех вершин.(необязательно напрямую)
Re: графы?да, графы?
Ну тогда и правда сконденсировать граф, и истоком будет любая из вершин, которая в сжатом графе стала вершиной степени входа 0, а стоком - любая вершина, соответствующая в сжатом графе вершине с степенью выхода 0.
Re: графы?да, графы?
С истоком согласен.А вот если после конденсации останется граф:
1->2
1->3
Тогда стока вообще не существует,но у 2 и 3 степень входа -0.
бтв в задаче гарантировано что исток и сток существуют,но перебирать все компоненты со степенью входа равной 0 мне кажется неразумным.
6 2010-06-17 13:07:55 Отредактировано MSDN (2010-06-17 13:08:45)
Re: графы?да, графы?
Сконденсируем граф. Далее если в конденсации есть ровно 1 вершина со степенью входа 0, то это - база. База - множество вершин в графе из которых достижимы все вершины в графе. Но если вершин со степенью входа 0, больше одной - то базы нет. На самом деле очевидно почему.... так как из одной вершины со степенью входа 0 нельзя достичь другой такой же.
Аналогично - если в графе есть ровно одна вершина со степенью выхода 0, то это - антибаза. Антибаза - множество вершин доступное из всех вершин графа. Также если их больше одной то антибазы нету...
Re: графы?да, графы?
Спасибо 