Avitella's blog

By Avitella, 11 years ago, In Russian

Дан ориентированный граф. Количество вершин порядка десяти в четвертой, количество ребер порядка десяти в пятой. Нужно найти минимальное количество ребер так, чтобы граф стал сильно связным. Как это сделать? Я понимаю, что нужно разделить граф на компоненты сильной связности, потом подсчитать у стольких компонент нет исходящих ребер и у скольких нет входящих. Ответом будет максимум из этих чисел. Проблема в том, что я не могу понять, как потом эти ребра построить.

  • Vote: I like it
  • +17
  • Vote: I do not like it