Advertisement
freeman701

Untitled

Jun 20th, 2020
1,041
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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.     stack[++stack_pointer] = 0;
  13.     while (stack_pointer >= 0)
  14.     {
  15.         int pop = stack[stack_pointer--];
  16.         if (visited[pop] == 0)
  17.         {
  18.             visited[pop] = 1;
  19.         }
  20.         if (visited[pop] == -1)
  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.         {
  51.             locked[winner][loser] = false;
  52.         }
  53.     }
  54.     return;
  55. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement