Cs50 Tideman Solution · Newest

In a directed graph, adding an edge from A → B creates a cycle if and only if B can already reach A.

Every year, the village of Coderidge held an election for the Keeper of the Orchard. Unlike other villages, they used a complex ranked voting system designed by a long-dead mathematician named Tideman. The rule was simple: if there was a way to trace a circle of preference (A beats B, B beats C, C beats A), that circle was a paradox, and the weakest link in that circle must be ignored.

Maya submitted her solution. And in the real election that followed, Alice became Keeper of the Orchard—not because she was the strongest in every head-to-head match, but because when paradoxes arose, the village had a coder wise enough to know which locks to leave open. Don't just check for a two-step loop. Use depth-first search to see if the loser has any path to the winner in the existing locked graph. If yes, skip the pair. That’s the entire secret of Tideman. Cs50 Tideman Solution

"Yes," Maya sighed. "I sort the pairs. Strongest first. Alice over Bob? Lock it. Bob over Charlie? Lock it. Charlie over Alice? Don't lock it because it creates a cycle. But my cycle detection is wrong."

She stared at her lock_pairs function. It was midnight. Her screen showed the dreaded red “:(” from check50 . In a directed graph, adding an edge from

Her friend, an old sysadmin named Kai, peered over her shoulder. "You're trying to lock every pair in order of strength, right?"

The story is useful because the narrative (the cycle, the DFS, the "path back") sticks in your brain longer than any pseudocode. Next time you face Tideman, remember Maya and the Orchard. The rule was simple: if there was a

"It's not about the edge you're adding," she whispered. "It's about the path that already exists beneath it."