Обнаружение циклических пар

Question

Предположим, что 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 

Я не хочу использовать любую Экстерну библиотеку (C++ библиотеки разрешена), так как функция bool isCyclic(const std::set< std::pair<char, char> >& set); будет использоваться только один раз, и она должна быть избыточна для #include большой библиотекой, как импульс только для этой одной функции ...

Любые идеи, как решить эту проблему?

Answer 1

У вас есть график, символы которого являются его вершинами и парами в наборе - ребрами. Вы можете легко определить, существует ли цикл, используя любой поиск, например, BFS или DFS. Также посмотрите на this question. Не против, что он имеет дело с неориентированным случаем, поскольку алгоритм один и тот же.