Задача. Пункт назначения
Задача. Дан массив paths, где paths[i] = [cityAi, cityBi] означает, что существует прямой путь из cityAi в cityBi.
Необходимо вернуть город назначения, то есть город, из которого нет ни одного пути, выходящего в другой город.
Уточнение. Гарантируется, что граф путей образует линию без каких-либо петель, поэтому город назначения будет ровно один.
Paths = [["B","C"],["D","B"],["C","A"]]
Output: "A"
Примечание: "B" -> "C" -> "A"
Разбор
Другими словами нам нужно найти город, который бы не находился 1м в паре [cityAi, cityBi], то есть из него нет ни одного пути.
Для решения этой задачи подойдет хэш-сет. В 1м цикле мы закинем в хэш-сет все города cityAi из каждой пары. А вторым циклом найдем такой город cityBi, которого нет в хэш-сете. Такой город и будет городом назначения.
Реализация
public static string DestinationCity(IList<IList<string>> paths)
{
int len = paths.Count;
// частный случай
if (len == 1) {
return paths[0][1];
}
// запоминаем все города отправления
var set = new HashSet<string>();
for (int i = 0; i < len; i++)
{
set.Add(paths[i][0]);
}
// находим 1й город назначения
for (int i = 0; i < len; i++)
{
if (!set.Contains(paths[i][1])) {
return paths[i][1];
}
}
return "";
} https://gist.github.com/unilecs/78f9a9b725fe26a881f0cab0da531dfe