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 | + |