python - 我的算法不正确。为什么这样？

Question

我正在尝试解决 the following problem :

The group of people consists of N members. Every member has one or more friends in the group. You are to write program that divides this group into two teams. Every member of each team must have friends in another team.

Input: The first line of input contains the only number N (N ≤ 100). Members are numbered from 1 to N. The second, the third,…and the (N+1)th line contain list of friends of the first, the second, …and the Nth member respectively. This list is finished by zero. Remember that friendship is always mutual in this group.

Output: The first line of output should contain the number of people in the first team or zero if it is impossible to divide people into two teams. If the solution exists you should write the list of the first group into the second line of output. Numbers should be divided by single space. If there are more than one solution you may find any of them.

我的算法是这样的:

create a dictionary where each player maps to a list of friends

team1 = ['1']
team2 = []

left = []

for player in dictionary:
    if its friend in team1:
        add to team2
    elif its freind in team2:
        add to team1
    else:
        add it to left

但还是不对。字典里可能有循环，6的 friend 是7，7的唯一 friend 是6，这种情况怎么办？我不知道这样一个周期会持续多久。我应该怎么办。因为，我的代码有一个 while 循环，我目前正在运行一个无限循环。我还尝试将 left 中的玩家添加到团队中，但它不起作用，因为它们之间存在循环。我不知道如何解决以下问题。

谢谢。

Answer 1

因为这是一个竞争问题，很明显你想从中学习，我会稍微简化细节并详细解释我是如何考虑这个问题的。

首先，考虑一个连接的友谊组件，然后选择任何顶点。由于友谊关系是可交换的，很容易看出添加一条边意味着两个顶点都“已解决”。这似乎暗示了类似寻找 perfect matching 的东西。 .

但是，仅仅找到一个完美匹配是不够的，对于三个顶点的完全图，完美匹配是不存在的，但它是可以求解的。所以稍微多想一下，似乎是一个Hamiltonian path就足够了，因为你可以更换团队。

如果您考虑的是一棵足够大的树，则应该清楚不存在哈密顿路径，但按偶数或奇数高度明显划分团队会产生正确的结果。所以答案似乎是，如果你能找到一棵生成树，那棵树就可以用来将团队一分为二。

这可以对每个组件重复进行，只是玩弄图表，它应该足以让比赛有说服力，因为每个组件都有一个生成树，所以没有其他地方可以扩展。我不确定什么是没有可能分配的图表。也许如果你有一个未连接的节点，那会被认为是无效的吗？