Задача
Черная дыра в ориентированном графе – слабо связный подграф (т.е. связный, если не учитывать направление ребер), из каждой вершины которого исходящие ребра могут идти только в вершины этого же подграфа. Иными словами, в черную дыру могут вести ребра из остальных вершин графа, обратно – нет.
Цель задачи – найти как можно большее количество черных дыр фиксированного размера в графе за ограниченное время (1 минута) на 8 узлах кластера.
Тестовые системы
Правила
  • Язык C/C++ и технологии MPI и OpenMP.
  • Можно использовать любой алгоритм.
  • Рейтинг участника определяется суммарным количеством найденных черных дыр на всех тестах.
  • Тест – граф и размер черных дыр, которые необходимо найти.
  • Тесты фиксированные и одинаковые для всех участников. Тестовые графы разных размеров, от нескольких сотен до миллиардов ребер.
  • В примере на C++ реализовано решение задачи (полный перебор). Немного улучшив пример реализации, даже неопытные участники могут легко попасть в таблицу результатов.
  • В случае, если у двух или более участников будет одинаковый результат, выше в таблице будет находиться участник, который отправил решение раньше.
Принять участие
  • Начать решать задачу можно уже сейчас.
  • Доступ на кластер осуществляется с помощью SSH начиная с 10-го сентября 2018 года.