可以由给定的广告对形成按字典顺序排列的更小的广告序列

Question

最近我做了Flipkart Online评估，我被一个问题卡住了很长一段时间。问题是这样的。一家广告公司有一系列广告对，每个广告都应该一个接一个地播放。如果给予“ABC”广告，对公司来说是有利的。我们必须找到所有广告至少播放一次的顺序。如果可能有多种这样的方式，请按字典顺序给出较小的一种。

例如：

4 
"XYZ", "IOP" 
"QWE", "XYZ" 
"ABC", "TUV" 
"TUV", "QWE"

可能的顺序是从“ABC”->“TUV”->“QWE”->“XYZ”->“IOP”开始

在规定的时间内我无法想出办法。经过我的思考，这与查找从源开始连通图是否可能是相似的，然后查看最小的顺序。

如果其他方法也可行，有人可以帮助我吗？或者这是推论的正确方法吗？

Answer 1

算法：

您需要创建一个邻接列表，以便子节点按字典顺序排序。

在 C++ 中，你可以使用向量的向量来做到这一点，在这里：

vector<pair<string,vector<string>> adjList

例如：

// not your example but a case when two ads can be shown after ABC
// preference should be for EFG over TUV
ABC -> EFG, TUV

您需要一张地图来标记已访问过的位置，数据结构为：

您必须在此图上执行图遍历，以便访问所有节点。 在遍历过程中，如果您已到达末尾且未标记所有已访问的节点，则需要在向后遍历时将它们标记为未访问。

如果您仍有疑问或答案中缺少某些内容，请告诉我。