Why isn't that algorithm working to detect cycles?

为什么这个算法不能检测周期呢？

// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
    // array[0] being true means that there is an edge or more pointing at candidate number 0
    bool array[candidate_count];
    for (int l = 0; l < pair_count; l++)
    {
        // add an edge, as long as it doesn't make a cycle
        if (!will_cycle(array, pairs[l].loser))
        {
            locked[pairs[l].winner][pairs[l].loser] = true;
            array[pairs[l].loser] = true;
        }
    }
}
// index is the index of the candidate the edge will be pointing at if it's added
// the function temporarily sets array[index] as true, like there's an edge pointing at it
// the function then iterates over all the array array, if they're all true it means there'll be a cycle.
// so it's undo the array[index] to false again.
// and if there's at least one false in the array array, it means there won't be a cycle
bool will_cycle(bool array[], int index) // return true if it will make a cycle
{
    array[index] = true;
    int flag = 0; // var for number of true candidates
    for (int i = 0; i < candidate_count; i++)
    {
        if (array[i])
            flag++;
    }

    if (flag == candidate_count) // they're all true
    {
        array[index] = false;
        return true;
    }
    return false;
}

Although (in my understanding) a cycle in the graph means a graph with no source, and a source is a candidate with no edges pointing at them, so the "array" array being all true means all candidates are having at least one edge pointing at them, so it's a cycle.

虽然(在我的理解中)图中的循环意味着没有源的图，而源是没有指向它们的边的候选者，所以“数组”数组为全真意味着所有候选者至少有一条边指向它们，所以这是一个循环。

Why can't that pass check50 test regarding lock_pair skipping pairs that will lead to a cycle, although I tested it and it worked fine?
Why do I have to use some sort of algorithm like DFS, why check50 doesn't like that?

为什么不能通过check50测试关于lock_pair跳过对，这将导致一个周期，虽然我测试了它，它工作正常？为什么我必须使用某种算法，比如DFS，为什么check50不喜欢这样？

I tried testing the example of Alice, Charlie and Bob found on background header in the pset page on cs50 website. I traced it, and I saw my algorithm just worked fine in skipping the last pair (which gave a cycle), and it even gave the correct winner's name.

我试着测试了在CS50网站的pset页面的背景标题上找到的Alice、Charlie和Bob的例子。我追踪了一下，我发现我的算法跳过了最后一对(给出了一个循环)，而且它甚至给出了正确的获胜者的名字。

The problem is that your understanding of what a cycle is in a graph is incorrect.

问题是，你对图中圈的理解是不正确的。

A graph has a cycle if there is a path that leads from a node back to itself. So for example A->B->C-A has as cycle. No matter what other edges you add to it, there is an 'infinite' path that can be made from A back to A. That is what we dont not want.

一个图有一个圈，如果有一条路径从一个节点回到它自己。例如，A->B->C-A有一个循环。无论你给它加上什么样的边，都有一条从A回到A的“无限”路径。这就是我们不想要的。

As a result your code to a cycle is flat out wrong.
Consider you have 5 candidates, a,b,c,d,e
if you have pairs (a,b), and (b,c) you can't add (c,a) because that would produce a cycle. a->b->c->a

因此，您对循环的代码是完全错误的。假设你有5个候选者，a，b，c，d，e，如果你有对(a，b)，而(b，c)你不能加上(c，a)，因为这会产生一个循环。A->b->c->a

So the problem is your algorithm is wrong. Further you are not using a depth first search. You aren't traversing the depth at all. The only thing you are doing is checking if this would make every single candidate a loser to someone. which is not the base case. This is however very close to what you would need to do to detect a winner in the next step. The winner is the node which is only a source and has no edges leading into it.

所以问题是你的算法是错误的。此外，您没有使用深度优先搜索。你根本不是在穿越深度。你做的唯一一件事就是检查这是否会让每个候选人都成为某个人的输家。这不是基本情况。然而，这与您在下一步中检测赢家所需的操作非常接近。赢家是节点，它只是一个源，没有通向它的边。

You need to ask yourself what are you looking for, what would occur if there was a cycle? and then prevent that.. There are a number of ways to do it. You could walk from winner to loser continually until you found there either was a cycle or there wasn't. You can see if you start from the loser and go backwards if theres locked pair where your path of losers is ever the winner over your initial winner. In all cases you will need to pass in initially both members of the pair you are proposing to add to the graph.

你需要问问自己，你在寻找什么，如果有一个周期，会发生什么？然后防止这种情况发生..有很多方法可以做到这一点。你可以不断地从一个赢家走到另一个输家，直到你发现要么有一个循环，要么没有。你可以看看你是否从输家开始，然后倒退，如果你的输家之路是赢家，而不是你最初的赢家。在所有情况下，您都需要首先传入您建议添加到图表中的两个成员。