Directed graphs, topological sort, and a presentation in the middle
Contents
Shorter day. Real reason. No guilt.
Had a presentation today.
Life doesn’t pause for a DSA challenge, and I’m not going to pretend otherwise. I got through fewer problems than planned — but I got through them properly, and I’m stopping here rather than grinding half-asleep and absorbing nothing.
That’s a conscious call, not a excuse.
The topics today were meatier anyway.
Cycle detection in directed graphs, topological sort, Kahn’s algorithm.
These are the ones that feel simple until you’re implementing them and something quietly goes wrong.
What I covered
Bipartite check — DFS version
Same idea as BFS: try to 2-color the graph, fail if two neighbors share a color. The trap here is nested if-else. It looks right when you write it, reads right when you skim it, and breaks in a specific case you won’t catch until you dry run it. Write the conditionals slowly and cleanly — don’t trust your first read.
Cycle detection in a directed graph — path visited matters
This one is different from undirected. A single visited[] array isn’t enough. You need a pathVisited[] too — tracking nodes on the current DFS path. Visiting a node that’s already in your current path means cycle. Visiting one that was explored in a different path doesn’t. It has a backtracking feel to it: you mark path-visited on entry, unmark on return. Easy to forget the unmark.
Know your graph type before building the adjacency list
Directed vs undirected changes how you add edges. Undirected: add both ways. Directed: one way only. Sounds obvious, costs you 10 minutes in a contest when you get it wrong silently.
Topological sort — DFS with a stack
Only works on DAGs — directed acyclic graphs. If there’s an edge A→B, A appears before B in the result. Multiple valid orderings can exist. The implementation is just DFS: fully explore a node, then push it to a stack. Pop the stack at the end for the order. Clean once you see it.
Kahn’s algorithm — BFS-based topo sort
Count indegrees. Push all zero-indegree nodes to a queue. Process them one by one: remove from queue, add to result, reduce neighbors’ indegrees. If a neighbor hits zero, enqueue it. No visited[] needed — a node only enters the queue when nothing points to it anymore. If the result doesn’t include all nodes, there was a cycle.
Cycle detection via Kahn’s — cleaner than it sounds
The DFS stack approach can’t detect cycles. Kahn’s can. Run it, check if topo result size equals total nodes. If not, some nodes’ indegrees never reached zero — meaning they were stuck in a cycle and never got added. Course Schedule I and II are exactly this problem, just dressed differently.
Conclusion
Graphs continue tomorrow. I’d rather finish this section properly than rush it to stay on schedule and have shaky foundations going into the contest on the 23rd. The plan is a guide, not a contract.
Day 2 done. Imperfect. Still counts.
And the presentation went well.
