View difference between Paste ID: ZcRKVmXw and t1gXAKxN
SHOW: | | - or go back to the newest paste.
1
// Check if there is still cycles in the graph or not
2
bool is_cycle()
3
{
4
    int stack[candidate_count];
5
    int visited[candidate_count];
6
    for (int i = 0; i < candidate_count; i++)
7
    {
8
        visited[i] = -1;
9
    }
10
    int stack_pointer = -1;
11
12-
	
12+
13-
	// Depth-first search implementation
13+
    while (stack_pointer >= 0)
14
    {
15-
    while (stack_pointer > 0)
15+
16
        if (visited[pop] == 0)
17
        {
18
            visited[pop] = 1;
19
        }
20-
            visited[pop] = -1;
20+
21
        {
22
            visited[pop] = 0;
23
        }
24
25
        for (int i = 0; i < candidate_count; i++)
26
        {
27
            if (locked[pop][i] && visited[i] == 1)
28
            {
29
                return true;
30
            }
31
            if (locked[pop][i])
32
            {
33
                stack[++stack_pointer] = i;
34
            }
35
        }
36
    }
37
    return false;
38
}
39
40
// Lock pairs into the candidate graph in order, without creating cycles
41
void lock_pairs(void)
42
{
43
    for (int i = 0; i < pair_count; i++)
44
    {
45
        int winner = pairs[i].winner;
46
        int loser = pairs[i].loser;
47
48
        locked[winner][loser] = true;
49
        if (is_cycle())
50-
		// lock the pair until it is proven otherwise
50+
51
            locked[winner][loser] = false;
52
        }
53
    }
54-
			// if there is a cycle, unlock the pair
54+
55-
            locked[winner][loser] = true;
55+