Две разные вершины в ориентированном графе сильно связаны, если в графе есть путь от одного к другому. Сильно компонента связности графы является подмножеством графа таким образом, что каждая пара различных вершин в подгруппе сильно связана, и добавление каких - либо больше вершин к подмножеству бы нарушить это свойство.

Ваша задача состоит в том, чтобы разделить график на его сильно связанные компоненты. В частности, вы должны вывести все SCC на графике.

I / O:

В качестве входных данных вы можете использовать список направленных ребер, список смежности, матрицу смежности или любой другой приемлемый формат ввода. Спросите, если вы не уверены. Вы можете предположить, что граф не имеет полностью несвязных вершин и что нет собственных ребер, но вы не можете делать никаких дополнительных предположений. Вы также можете при желании принять список вершин в качестве входных данных, а также количество вершин.

В качестве выходных данных вы должны либо дать разбиение вершин, например, список списков вершин, где каждый подсписок является сильно связным компонентом, либо метку вершин, где каждая метка соответствует отдельному компоненту.

Если вы используете метки, метки должны быть либо вершинами, либо последовательной последовательностью целых чисел. Это сделано для того, чтобы избежать смещения вычислений в метки.

Примеры:

В этих примерах используются списки ребер, где каждое ребро направлено от 1-й записи ко второй записи, и выходные разделы. Вы можете использовать этот формат или другой.

Вход находится в первой строке, выход - во второй.

[[1, 2], [2, 3], [3, 1], [1, 4]]
[[1, 2, 3], [4]]

[[1, 2], [2, 3], [3, 4]]
[[1], [2], [3], [4]]

[[1, 2], [2, 1], [1, 3], [2, 4], [4, 2], [4, 3]]
[[1, 2, 4], [3]]

[[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]
[[1, 2, 5], [3, 4, 8], [6, 7]]

Подсчет очков и ограничения:

Стандартные лазейки , как всегда, запрещены. Кроме того, встроенные модули, которые специально работают с сильно связанными компонентами, запрещены.

Решения должны выполняться не более часа на предоставленных примерах. (Это предназначено для предотвращения медленных экспоненциальных решений и ничего больше.)

Это код гольф. Побеждает несколько байтов.

Python 2 с использованием numpy, 71 62 байта

import numpy
def g(M,n):R=(M+M**0)**n>0;print(R&R.T).argmax(0)

Принимает входные данные в виде numpyматрицы, представляющей смежность и количество узлов. Производит вывод в виде numpyматрицы строк, которая помечает каждую вершину наименьшим номером вершины в ее компоненте.

Для матрицы смежности Mмощность матрицы M**nподсчитывает количество n-шаговых путей от каждой начальной вершины до каждой конечной вершины. Добавление идентификатора в Mvia M+M**0изменяет матрицу смежности, добавляя цикл к каждому ребру. Таким образом, (M+M**0)**nучитывается длина пути не более n(с избыточностью).

Поскольку любой путь имеет длину не более n , число узлов, из (i,j)которых jможет быть достигнута вершина, iсоответствует положительной записи в (M+M**0)**n. Матрица достижимости тогда R=(M+M**0)**n>0, где >0работает входно.

Вычисляя входное значение andкак R&R.T, где R.Tтранспонирование, затем дает матрицу, указывающую пары взаимно достижимых вершин. Эта iстрока является вектором-индикатором для вершин в том же сильно связанном компоненте, что и он. Взятие argmaxкаждой строки дает индекс первой Trueв нем, который является индексом самой маленькой вершины в ее компоненте.

JavaScript (ES6), 125 байт

a=>a.map(([m,n])=>(e[m]|=1<<n|e[n],e.map((o,i)=>o&1<<m?e[i]|=e[m]:0)),e=[])&&e.map((m,i)=>e.findIndex((n,j)=>n&1<<i&&m&1<<j))

Принимает список направленных пар в качестве аргумента, в то время как результатом является массив для каждой вершины, дающий первую вершину, тесно связанную с ней, которая, я считаю, считается допустимой маркировкой. Например, со входом, который [[1, 2], [2, 3], [2, 5], [2, 6], [3, 4], [3, 7], [4, 3], [4, 8], [5, 1], [5, 6], [6, 7], [7, 6], [8, 7], [8, 4]]он возвращает [, 1, 1, 3, 3, 1, 6, 6, 3](вершины 0 нет; вершины 1, 2 и 5 имеют метку 1; 3, 4 и 8 имеют метку 3, а 6 и 7 имеют метку 6).

MATL , 26 22 байта

tnX^Xy+HMY^gt!*Xu!"@f!

Это использует тот же подход, что и ответ @ xnor .

Работает в текущей версии (15.0.0) языка.

Входные данные - это матрица смежности графа, строки которой разделены точкой с запятой. Первый и последний контрольные примеры

[0 1 0 1; 0 0 1 0; 1 0 0 0; 0 0 0 0]

[0 1 0 0 0 0 0 0; 0 0 1 0 1 1 0 0; 0 0 0 1 0 0 1 0; 0 0 1 0 0 0 0 1; 1 0 0 0 0 1 0 0; 0 0 0 0 0 0 1 0; 0 0 0 0 0 1 0 0; 0 0 0 1 0 0 1 0]

Попробуйте онлайн!

t     % implicitly input adjacency matrix. Duplicate
n     % number of elements
X^    % square root
Xy    % identity matrix of that size
+     % add to adjacency matrix
HM    % push size again
Y^    % matrix power
g     % convert to logical values (0 and 1)
t!*   % multiply element-wise by transpose matrix
Xu    % unique rows. Each row is a connected component
!     % transpose
"     % for each column
  @   %   push that column
  f!  %   indices of nonzero elements, as a row
      % end for each. Implicitly display stack contents

Pyth, 13 байт

.gu+Gs@LQG.{k

Демонстрация , Тестовый пакет

Ввод - это список смежности, представленный в виде словаря, который отображает вершины в список вершин, к которым у него есть ребра (у его направленных соседей). Выход - это раздел.

Суть программы заключается в том, что мы находим набор вершин, которые достижимы из каждой вершины, а затем группируем вершины по этим наборам. Любые две вершины в одном и том же SCC имеют одинаковый набор вершин, достижимых из них, потому что каждая достижима из другой, и достижимость транзитивна. Любые вершины в разных компонентах имеют разные достижимые множества, потому что ни один из них не содержит другого.

Объяснение кода:

.gu+Gs@LQG.{k
                  Implicit: Q is the input adjacency list.
.g           Q    Group the vertices of Q by (Q is implicit at EOF)
  u       .{k     The fixed point of the following function, 
                  starting at the set containing just that vertex
   +G             Add to the set
     s            The concatenation of
      @LQG        Map each prior vertex to its directed neighbors