Write nested loops as linq query
create a lookup of all tracked trains for each wagon


That's pretty much what the ToLookup() method is for. You just need a bit more LINQ  to get a collection of (train, wagon) pairs, so that ToLookup() can work:

var wagonTrains =
    (from train in trains
     from wagon in train.WagonsInTrain
     select new { train, wagon })
        .ToLookup(x =&gt; x.wagon, x =&gt; x.train);