Найти головку цепочки ссылок

Question

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

[ [a, b], [a, c], [d, c] ] 

Это данность, что первый элемент является первым звеном в цепи. Я изначально хотел отобразить пары в объект map/value map, а затем пройти через ключи и/или значения, чтобы найти голову.

упрощенный алгоритм:

keys.contains(a) || values.contains(a) 

если либо возвращает TRUE (за исключением самой пары, естественно), то это не голова. Итак, начиная с первой пары, keys.contains (a) || values.contains (a) возвращает true, так что это не голова, а keys.contains (b) || values.contains (b) возвращает false - так что это должна быть голова.

Проблема: я не могу сопоставить пары в объекте, так как могут быть дубликаты клавиш/значений, которые переопределяют друг друга.

т.е. для приведенных выше примеров, результирующий объект будет:

{ 
    a: c, 
    d: c 
} 

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

Любые идеи более эффективного решения?

Answer 1

Я предполагаю, что источником является ключ, а пункт назначения - значение. Корни вашего ориентированного графа - это те ключи, которые не имеют значения. (Листья: наоборот).

a будет корень, а также d. b и c - нет. Ваше состояние должно быть keys.contains(a) && !values.contains(a).

Возможно, у вас нет корня, если объекты указывают друг на друга ([ [a, b], [b, a] ]) или что-то указывает на себя ([ [a, a] ]).

Теперь, если вы устраните самореференции, вы можете получить ключи и значения. Чтобы получить корни, вы перебираете ключи и проверяете, не являются ли они значениями. Чтобы получить листья, вы перебираете значения и проверяете, не являются ли они ключом.

HTH, но я не уверен, что правильно понял ваш вопрос.