C# - 遍历对和匹配

Question

所以我被困在一个程序中，我有一系列对，这些对可能会也可能不会连接在一起以形成通过这些对的完整路径。我需要能够检查一对中的第二个项目是否可以匹配另一对中的第一个项目，依此类推，直到没有对为止。例如，我的对可能是:

(1,5)
(2,4)
(3,2)
(5,3)
(4,3)

我需要能够以某种方式遍历这些对，并根据一对中的第二个数字是否与下一对中的第一个数字匹配来检查我是否可以获得穿过每个对的完整路径。在此示例中，输出将是:

(1,5), (5,3), (3,2), (2,4), (4,3)

形成一个完整的匹配。如果无法匹配，我需要报告失败。输入基于文本文件。到目前为止，我已经能够使用 Streamreader 读取文件并根据换行符拆分对，然后遍历并根据逗号将每一对拆分为其项目。我对如何进行几乎一无所知，如果有人有一些想法，我将不胜感激。

StreamReader sr = new StreamReader("inputs.txt");
string line = null;
line = sr.ReadToEnd();
var str = line.Trim().Split('\n');
int length = str.Length;
int index=1;

while (index < length)
{
    var pair = str[index].Split(',');
    var item1 = pair[0];
    var item2 = pair[1];
}

Answer 1

你描述的问题可以转化为另一种形式；一个graph .

这是您给出的示例的样子。

我画了一个从 1 到 5 的箭头，因为有一对 (1,5) 等。

像这样的图上的路径只能沿着箭头的方向。

您想知道的是:“此图中是否存在使用每一对的路径，即遍历每条边？”

这样的路径被称为 Eulerian Directed Path

维基百科列出了两种用于查找此类路径的算法，即 Fleury 和 Hierholzer，这两种算法都是在 1800 年代后期发现的。希望这能让您了解从哪里开始解决这个问题。