c++ - 检测循环对

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

我不想使用任何 extern 库（允许使用 c++ 库），因为该函数bool isCyclic(const std::set< std::pair<char, char> >& set);只会被使用一次，而且对于#include像 boost 这样的大型库来说，对于那个函数来说它应该是矫枉过正的......

任何想法如何解决这个问题？

Answer 1

你在这里有一个图，字符是它的顶点和集合中的对 - 边。您可以使用任何搜索轻松检测是否存在循环，例如BFS或DFS。也看看这个问题。不要介意它处理无向案例，因为算法是相同的。