in lock pair (lock_pairs skips final pair if it creates cycle is working) rest all lock_pair and print winner is not working.
#include <cs50.h>
#include <stdio.h>
#include <string.h>
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);
void swap(pair *a, pair *b);
bool check(int x, int y, int i);
bool win(int a);
int main(int argc, string argv[])
{ // Check for invalid usage
if (argc < 2)
{
printf("Usage: tideman [candidate ...]\n");
return 1;
}
// Populate array of candidates
candidate_count = argc - 1;
if (candidate_count > MAX)
{
printf("Maximum number of candidates is %i\n", MAX);
return 2;
}
for (int i = 0; i < candidate_count; i++)
{
candidates[i] = argv[i + 1];
}
// Clear graph of locked in pairs
for (int i = 0; i < candidate_count; i++)
{
for (int j = 0; j < 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 < voter_count; i++)
{
// ranks[i] is voter's ith preference
int ranks[candidate_count];
// Query for each rank
for (int j = 0; j < 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[])
{
for (int i = 0; i < 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[])
{
for (int i = 0; i < candidate_count; i++)
{
for (int j = i + 1; j < candidate_count; j++)
{
preferences[ranks[i]][ranks[j]]++;
}
}
return;
}
// Record pairs of candidates where one is preferred over the other
void add_pairs(void)
{
int m = candidate_count;
for (int k = 0; k <= (m * (m - 1) / 2); k++)
{
for (int i = 0; i < candidate_count ; i++)
{
for (int j = 0; j < candidate_count ; j++)
{
if (preferences[i][j] > 0)
{
pairs[k].winner = i;
pairs[k].loser = j;
pair_count++;
}
}
}
}
pair_count = pair_count - 1;
return;
}
// Sort pairs in decreasing order by strength of victory
void sort_pairs(void)
{ int m = pair_count;
for (int i = 0; i < m ; i++)
{
for (int j = 0; j < m - 1; j++)
{
for (int k = j + 1; k <= j + 1; k++)
{
if (preferences[pairs[j].winner][pairs[j].loser] < preferences[pairs[k].winner][pairs[k].loser])
{
swap(&pairs[j], &pairs[k]);
}
}
}
}
return;
}
void swap(pair *a, pair *b)
{
pair tmp = *b;
*b = *a;
*a = tmp;
}
bool check(int x, int y, int i) //check for cycle // returns true if no cycle
{
for (int k = i - 1; k >=0; k--)
{
if (pairs[i].loser == pairs[k].winner)
{
return false;
}
}
return true;
}
// Lock pairs into the candidate graph in order, without creating cycles
void lock_pairs(void)
{
locked[pairs[0].winner][pairs[0].loser] = true;
locked[pairs[1].winner][pairs[1].loser] = true;
for (int i = 2; i < pair_count; i++)
{
if (check(pairs[i].winner, pairs[i].loser, i) == true)
{
locked[pairs[i].winner][pairs[i].loser] = true;
}
}
return;
}
// Print the winner of the election void print_winner(void) { for (int i = 0; i < pair_count; i++)
{
if(locked[pairs[i].winner][pairs[i].loser] == true)
{
if (win(i) == true)
{
printf("%s", candidates[pairs[i].winner]);
}
}
}
return;
}
bool win(int a) { for (int j = 0; j < pair_count; j++)
{
if (locked[pairs[j].winner][pairs[j].loser] == true)
{
if (pairs[a].winner == pairs[j].loser)
{
return false;
}
}
}
return true;
}
