title: How to check for cycles in a graph?
body: <p>My code works fine but fails check50 test for skipping pairs when creating cycles. The logic I use to check for cycles is that before creating an edge from winner to loser I go back the edges from the winner and check if it ever reaches the loser. If it does, it means it'll create a cycle so the edge is skipped but It doesn't work. My logic could be wrong too, if so let me know. Here's my code-</p>
  
  <pre><code>#include &lt;cs50.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  
  // Max number of candidates
  #define MAX 9
  
  // preferences[i][j] is number of voters who prefer i over j
  int preferences[MAX][MAX];
  
  // locked[i][j] means i is locked in over j
  bool locked[MAX][MAX];
  
  // Each pair has a winner, loser
  typedef struct
  {
      int winner;
      int loser;
  }
  pair;
  
  // Array of candidates
  string candidates[MAX];
  pair pairs[MAX * (MAX - 1) / 2];
  
  int pair_count;
  int candidate_count;
  
  // Function prototypes
  bool vote(int rank, string name, int ranks[]);
  void record_preferences(int ranks[]);
  void add_pairs(void);
  void sort_pairs(void);
  void lock_pairs(void);
  void print_winner(void);
  bool check_cycle(int n, int m);
  
  int main(int argc, string argv[])
  {
      // Check for invalid usage
      if (argc &lt; 2)
      {
          printf("Usage: tideman [candidate ...]\n");
          return 1;
      }
  
      // Populate array of candidates
      candidate_count = argc - 1;
      if (candidate_count &gt; MAX)
      {
          printf("Maximum number of candidates is %i\n", MAX);
          return 2;
      }
      for (int i = 0; i &lt; candidate_count; i++)
      {
          candidates[i] = argv[i + 1];
      }
  
      // Clear graph of locked in pairs
      for (int i = 0; i &lt; candidate_count; i++)
      {
          for (int j = 0; j &lt; candidate_count; j++)
          {
              locked[i][j] = false;
          }
      }
  
      pair_count = 0;
      int voter_count = get_int("Number of voters: ");
  
      // Query for votes
      for (int i = 0; i &lt; voter_count; i++)
      {
          // ranks[i] is voter's ith preference
          int ranks[candidate_count];
  
          // Query for each rank
          for (int j = 0; j &lt; candidate_count; j++)
          {
              string name = get_string("Rank %i: ", j + 1);
  
              if (!vote(j, name, ranks))
              {
                  printf("Invalid vote.\n");
                  return 3;
              }
          }
  
          record_preferences(ranks);
  
          printf("\n");
      }
  
      add_pairs();
      sort_pairs();
      lock_pairs();
      print_winner();
      return 0;
  }
  
  // Update ranks given a new vote
  bool vote(int rank, string name, int ranks[])
  {
      // TODO
      for (int i = 0; i &lt; candidate_count; i++)
      {
          if (strcmp(candidates[i], name) == 0)
          {
              ranks[rank] = i;
              return true;
          }
      }
  
      return false;
  }
  
  // Update preferences given one voter's ranks
  void record_preferences(int ranks[])
  {
      // TODO
      for (int i = 0; i &lt; candidate_count; i++)
      {
          for (int j = 1; j &lt; candidate_count - i; j++)
          {
              preferences[ranks[i]][ranks[i + j]]++;
          }
      }
  
      return;
  }
  
  // Record pairs of candidates where one is preferred over the other
  void add_pairs(void)
  {
      // TODO
      for (int i = 0; i &lt; candidate_count; i++)
      {
          for (int j = 0; j &lt; candidate_count; j++)
          {
              if (preferences[i][j] &gt; preferences[j][i])
              {
                  pairs[pair_count].winner = i;
                  pairs[pair_count].loser = j;
                  pair_count++;
              }
          }
      }
  
      return;
  }
  
  // Sort pairs in decreasing order by strength of victory
  void sort_pairs(void)
  {
      // TODO
      pair k;
      for (int i = 0; i &lt; pair_count; i++)
      {
          for (int j = i + 1; j &lt; pair_count; j++)
          {
              if (preferences[pairs[i].winner][pairs[i].loser] &lt; preferences[pairs[j].winner][pairs[j].loser])
              {
                  //memcpy
                  k = pairs[i];
                  pairs[i] = pairs[j];
                  pairs[j] = k;
              }
          }
      }
  
      return;
  }
  
  // Lock pairs into the candidate graph in order, without creating cycles
  void lock_pairs(void)
  {
      // TODO
      for (int i = 0; i &lt; pair_count; i++)
      {
          if (!check_cycle(pairs[i].winner, pairs[i].loser))
          {
              locked[pairs[i].winner][pairs[i].loser] = true;
          }
      }
      return;
  }
  
  // Print the winner of the election
  void print_winner(void)
  {
      // TODO
      for (int i = 0; i &lt; candidate_count; i++)
      {
          bool source = true;
  
          for (int j = 0; j &lt; candidate_count; j++)
          {
              if (locked[j][i] == true)
              {
                  source = false;
                  break;
              }
          }
  
          if (source == true)
          {
              printf("%s\n", candidates[i]);
          }
      }
  
      return;
  }
  
  //checking for cycle
  bool check_cycle(int n, int m)
  {
      if (locked[m][n] == true)
      {
          return true;
      }
  
      for (int i = 0; i &lt; candidate_count; i++)
      {
          if (locked[i][n] == true)
          {
              check_cycle(i, m);
          }
      }
      return false;
  }
  </code></pre>