检查是否存在一串始终通向同一顶点的方向
Checking if there exists a string of directions that always leads to same vertex
有一个图有 n 个顶点。每个都有 4 条边，分别代表世界的每一侧。所有这些都是定向的。我必须编写一个程序来检查是否存在一串始终指向相同顶点的方向，无论您从哪里开始。
例如：
如果你去 S W S，你将永远在 3。
不存在这样的路线。
我知道怎么做，但我需要一个大小为 2^n 的 bool 数组。但是，程序必须适用于 n 最大 1000。
最好的方法是什么？
您描述的这种字符串称为 synchronizing word. If you are just trying to test whether such a word exists, there's a polynomial-time algorithm 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} 到某个单例节点的路径时，原始图才具有同步词。
如果你在网上搜索，你可以找到关于这个主题的各种其他读物。希望术语和以上链接可以帮助您入门！
有一个图有 n 个顶点。每个都有 4 条边，分别代表世界的每一侧。所有这些都是定向的。我必须编写一个程序来检查是否存在一串始终指向相同顶点的方向，无论您从哪里开始。 例如：
如果你去 S W S，你将永远在 3。
不存在这样的路线。
我知道怎么做，但我需要一个大小为 2^n 的 bool 数组。但是，程序必须适用于 n 最大 1000。 最好的方法是什么？
您描述的这种字符串称为 synchronizing word. If you are just trying to test whether such a word exists, there's a polynomial-time algorithm 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} 到某个单例节点的路径时，原始图才具有同步词。
如果你在网上搜索，你可以找到关于这个主题的各种其他读物。希望术语和以上链接可以帮助您入门！