Обнаружение циклических пар
Предположим, std::set< std::pair<char, char> >Кто-нибудь может предложить алгоритм или подход, чтобы проверить, существуют ли циклические пары?
например
std::set< std::pair<char, char> > cyclic = { {'A', 'B'}, {'B', 'C'}, {'C', 'A'} };
std::set< std::pair<char, char> > not_cyclic = { {'A', 'B'}, {'B', 'C'}, {'C', 'C'} };
isCyclic(cyclic); // true
isCyclic(not_cyclic); // false
Я не хочу использовать какую-либо библиотеку extern (библиотека c ++ разрешена), так как функция bool isCyclic(const std::set< std::pair<char, char> >& set); будет использоваться только один раз, и это должно быть излишним #include большая библиотека вроде boost только для этой функции …
Есть идеи, как решить эту проблему?
Решение
То, что у вас есть, это график, символы которого являются его вершинами, а пары в наборе — ребрами. Вы можете определить, есть ли цикл, легко используя любой поиск, например BFS или же DFS,
Также посмотрите на этот вопрос. Не берите в голову, что это имеет дело с неориентированным случаем, поскольку алгоритм тот же.
Другие решения
Других решений пока нет …