algorithm - secret 圣诞老人算法

Question

每年圣诞节，我们都会为家里的礼物交换抽签。这通常涉及多次重画，直到没有人拉出他们的配偶。所以今年我编写了我自己的名字绘图应用程序，它接受一堆名字，一堆不允许的配对，并向每个人发送一封电子邮件，其中包含他们选择的礼物接收者。

现在，算法的工作原理如下(伪代码):

function DrawNames(list allPeople, map disallowedPairs) returns map
    // Make a list of potential candidates
    foreach person in allPeople
        person.potentialGiftees = People
        person.potentialGiftees.Remove(person)
        foreach pair in disallowedPairs
            if pair.first = person
               person.Remove(pair.second)

    // Loop through everyone and draw names
    while allPeople.count > 0
        currentPerson = allPeople.findPersonWithLeastPotentialGiftees
        giftee = pickRandomPersonFrom(currentPerson.potentialGiftees)
        matches[currentPerson] = giftee
        allPeople.Remove(currentPerson)
        foreach person in allPeople
            person.RemoveIfExists(giftee)

    return matches

对图论了解更多的人是否知道某种算法在这里会更好地工作？就我的目的而言，这可行，但我很好奇。

编辑:由于电子邮件在不久前发出，我只是希望能学到一些东西，所以我将其改写为图论问题。我对排除项都是成对的特殊情况不太感兴趣(比如配偶不互相了解)。我对排除项足够多以至于找到任何解决方案都变得困难的情况更感兴趣。我上面的算法只是一个简单的贪心算法，我不确定它在所有情况下都会成功。

从完整的有向图和顶点对列表开始。对于每个顶点对，删除从第一个顶点到第二个顶点的边。

目标是得到一个图，其中每个顶点都有一条边进入，一条边离开。

Answer 1

如果允许他们分享礼物，只需制作一个边连接两个人的图，然后使用完美匹配算法。 (为(聪明的)算法寻找“路径、树和花”)