Znajdywanie duplikatów w zagnieżdzonych N kolekcjach

Nie jestem dobry w algorytmice więc nie wiem jak zatytułować ten wątek. Mam taką zagwozdkę:

class Item
{
  public string Id { get; init; }
  public IList<Item> Items { get; init; } = new List<Item>();
}

class Root
{
  public IList<Item> Items { get; init; } = new List<Item>();
}

Więc obiekt typu Root ma teoretycznie nieograniczoną kolekcję obiektów typu Item, każda instancja Item ma teoretycznie nieograniczoną kolekcję instacji Item, gdzie każda instancja ma... Wiecie o co chodzi. To co ja muszę zrobić to dla każdego itemu wziąć jego ID, i upewnić się że żaden inny item zaczynając od roota nie ma takiego samego ID. Ktoś ma pomysł jak to zrobić żeby było w miarę zgrabnie i efektywnie? Jedyne co mi przychodzi do głowy to podejść do tego rekurencyjnie, ale nie wydaje mi się to efektywne zważywszy że dla każdego elementu trzeba by się zagnieżdżać w poszukiwaniu danego ID, i tak dalej dla każdego kolejnego elementu.

No jak masz taka strukturę (graf), to nie zrobisz tego szybciej niż liniowo - musisz odwiedzić każdy węzeł. Liniowo możesz to zrobić w ten sposób, że przechodzisz po grafie (np. rekurencyjnie) algorytmem DFS i utrzymujesz Set idków - w ten sposób wykryjesz duplikaty.

Zrobiłem to w ten sposób. Jak ktoś ma lepszy pomysł to dawajcie śmiało.

var root = new Root { ... };
var containsDuplicates = ContainsDuplicates(root);

bool ContainsDuplicates(Root root) =>
    SelectIDs(root.Items)
        .GroupBy(id => id)
        .Any(g => g.Count() > 1);

IEnumerable<int> SelectIDs(IList<Item> items)
{
    foreach (var item in items)
    {
        yield return item.Id;
        
        foreach (var id in SelectIDs(item.Items))
            yield return id;
    }
}

ja wole kueue niż rekurencje

var rut = new Root
{
    Items = new List<Item>()
    {
        new Item
        {
            Id = "1",
            Items = new []
            {
                new Item
                {
                    Id = "2",
                    Items = new []
                    {
                        new Item
                        {
                            Id = "3",
                            Items = new []
                            {
                                new Item
                                {
                                    Id = "3"
                                } 
                            }
                        }
                    }
                }
            }
        }
    }
};

var dict = new Dictionary<string, int>();
var q = new Queue<Item>(rut.Items); // initialize first level

// walk thru all
while (q.Count > 0)
{
    var current = q.Dequeue();

    dict[current.Id] = dict.ContainsKey(current.Id) ? ++dict[current.Id] : 1;

    foreach (var item in current.Items)
        q.Enqueue(item);
}

// display results
foreach (var item in dict)
    Console.WriteLine(item);

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

@1a2b3c4d5e: to też interesujące podejście. Chyba wolę rekurencję, ale z ciekawości odpalę benchmarki i sprawdzę oba.

To ma pewno są drzewa, nie masz jakiś cykli w referencjach? Jeśli tak to trzeba zapisywać informację czy wierzchołek był odwiedzony.

@Saalin: tutaj naprawdę nie ma co się doszukiwać drugiego dna. Każdy Item to unikalna instancja. Wbrew temu co podałem w przykładzie powyżej to używam recordów, w tym głębokie klony kolekcji. Rzecz tylko w tym aby upewnić się że gdzieś, przez przypadek nie został dodany obiekt z takim samym ID, to wszystko.

@1a2b3c4d5e: wychodzi na to że metoda z kolejką jest szybsza i zużywa mniej pamięci. Robiłem ten benchmark na szybko, z kolekcją zagnieżdżoną siedmiokrotnie. Więcej mi się nie chciało :P

Mała uwaga - jeśli to ma być DFS, to powinieneś użyć stosu, a nie kolejki.

Zawszę można użyć zamiast IList jakiegoś ISet i nadpisać equals na klasie Item i wiadomo, że nie będzie duplikatów :P