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

Предположим, 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 только для этой функции …

Есть идеи, как решить эту проблему?

0

Решение

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

0

Другие решения

Других решений пока нет …