Свести зазубренный массив по ссылке значений

Question

Учитывая неровный массив целых чисел, например:

var arr = new int[11][] { 
    new int[] { 0, 7 }, 
    new int[] { 1 }, 
    new int[] { 2, 5, 6 }, 
    new int[] { 3 }, 
    new int[] { 4 }, 
    new int[] { 5, 6 }, 
    new int[] { 6 }, 
    new int[] { 7, 9 }, 
    new int[] { 8, 10 }, 
    new int[] { 9 }, 
    new int[] { 10 } 
}; 

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

{ 0, 7, 9, 1, 2, 5, 6, 3, 4, 8, 10 } 

В этом конкретном примере, { 0, 7 } и { 7, 9 } будут объединены, поскольку они имеют общий номер, 7 связывая их. Кроме того, следующие дубликаты, такие как { 5, 6 }, { 6 } и т. Д. Удаляются.

Не уверен, что он имеет достаточный смысл, но я тоже царапаю голову :) Я надеюсь, что слишком много обратных ссылок, и можно избежать нескольких вложенных циклов, если возможно, может использоваться LINQ/PLINQ или некоторые умная манипуляция на месте.

Answer 1

Вашего примера результат может быть найден в результате topological sorting из DAG (ориентированный ациклический граф), где пары ваших подмассивов образуют ребра графа

{2,5,6} образует ребра направлены (дуги) 2-> 5 и 5-> 6.

Topo сортировки также обнаружат возможные противоречия (циклы), как {2,3}, {3,5}, {5,2}