Cs50 Tideman Solution

Subtitle: How I stopped worrying and learned to love the graph theory.

If you are currently taking CS50, you probably just felt a cold shiver run down your spine seeing the word "Tideman."

For those uninitiated, the Tideman problem (pset3) is the infamous "boss fight" of the early weeks. It takes the concepts of plurality and runoff elections and cranks the difficulty up to 11 by introducing a ranked-choice voting system that uses a directed graph. Cs50 Tideman Solution

Here is how I cracked it, and the specific logic that finally made the "click" happen.

The core unit of the Tideman algorithm is the pairwise comparison. A pair struct is defined to hold the indices of the winner and loser of a specific matchup: Subtitle: How I stopped worrying and learned to

typedef struct 
    int winner;
    int loser;
 pair;

To detect a cycle, we use a recursive depth-first search (DFS). The function cycle_check(int start, int end) determines if adding an edge from start to end closes a loop.

Remember: sort in descending order of victory margin: To detect a cycle, we use a recursive

int margin = preferences[pairs[i].winner][pairs[i].loser] - 
             preferences[pairs[i].loser][pairs[i].winner];

Use qsort() with a custom comparator that compares margins.