有一个具有 n 个顶点的图。每个都有 4 个边，一个代表世界的每一边。都是有指挥的。我必须编写一个程序来检查是否存在一串始终通向同一顶点的方向，无论从哪里开始。 例如:
如果你去S W S，你总是会在3。
这样的指示串不存在。
我知道如何做到这一点，但我需要一个大小为 2^n 的 bool 数组。但是，程序必须适用于 n 大小不超过 1000 的情况。 最好的方法是什么？
最佳答案
您所描述的字符串类型称为 synchronizing word 。如果您只是想测试这样的单词是否存在，可以使用多项式时间算法 described in these lecture slides 。直观上，对于每对节点 u 和 v，您构建一个新图，其中起始节点是对 {u, v}。每个节点都有一个在每个字符 c 上定义的到集合 {t(c, u), t(c, v)} 的转换，其中 t(c, u) 表示通过读取状态 u 中的字符 c 转换到的节点。您可以使用 DFS 或 BFS 扩展该图。原始图具有同步字当且仅当对于每对节点 {u, v}，上述过程生成一个具有从 {u, v} 到某个单例节点的路径的图。
如果您在线搜索，您可以找到有关该主题的各种其他读物。希望术语和上面的链接可以帮助您入门!
关于c++ - 检查是否存在一串始终通向同一顶点的方向，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34484266/