← Back to Cheat Sheets
Diff Toposort Quickunion
# Quick Comparison: Topological Sort vs Quick Union
| Feature | Topological Sort | Quick Union (Disjoint Set Union) |
|---|---|---|
| Purpose | Order nodes respecting dependency (DAGs only) | Find connected components and detect cycles (undirected graphs) |
| Works on | Directed graphs (DAGs) | Undirected graphs |
| Detects cycle? | ✅ (if cannot topologically sort, cycle detected) | ✅ (when two nodes already share a parent, cycle detected) |
| Handles direction of edges? | ✅ (Direction matters: u ➔ v) |
❌ (Ignores direction: just connected or not) |
| Output | Ordered list of nodes ([u, v, w]) |
Connected components or cycle detection |
| Common Use Cases | Course scheduling, build systems, dependency resolution | Kruskal’s MST, dynamic connectivity, union-find problems |
| Time Complexity | O(V + E) | Nearly O(1) per operation (amortized with path compression) |
| Space Complexity | O(V + E) | O(V) |
# 🏩 Conceptual Difference
| Topological Sort | Quick Union | |
|---|---|---|
| Respect dependency order | ✅ | ❌ |
| Is everything connected? | ❌ | ✅ |
| Detects directed cycles? | ✅ | ❌ |
# ⚙️ Algorithm Core Ideas
# ➔ Topological Sort (for DAGs)
- Think assembly line:
- Can’t assemble a car until frame is ready.
- Process nodes with no incoming edges first.
- If you ever get stuck (nodes still left but no “zero indegree” node), cycle detected.
Two common ways:
- BFS with indegree array.
- DFS with recursion + post-order.
# ➔ Quick Union (Disjoint Set Union)
- Think friend groups:
- If Alice knows Bob, Bob knows Charlie → one group.
- Each node points to a parent.
- If two nodes already have the same root → cycle detected (for undirected graphs).
- Heavily optimized with:
- Path Compression (flatten tree during find)
- Union by Rank/Size (attach smaller tree under larger one)
# 🚀 Visual Example
Imagine the same input:
Courses: 0 -> 1 -> 2
| Topological Sort | Quick Union | |
|---|---|---|
| What happens? | Outputs [0, 1, 2] (order matters) | Simply groups them together (connection matters, not order) |
| Why? | Because 0 must finish before 1, and 1 before 2 | Only cares that they’re connected |
| Cycle detection? | If a back edge exists (e.g., 2 ➔ 0) → cycle | If trying to connect two nodes already connected → cycle |
# 🧪 Analogy
-
Topological Sort is like building a skyscraper:
- Must finish floors bottom-up respecting the order.
-
Quick Union is like finding clusters of friends:
- Doesn’t matter who talked first, just find connected groups.
# 📜 Summary
| Question | Answer |
|---|---|
| Are they solving the same problem? | ❌ |
| Do both detect cycles? | ✅ (in different contexts) |
| Which one should I use for Course Schedule (directed graph)? | Topological Sort ✅ |
| Which one is faster per operation? | Quick Union (amortized ~O(1)) ✅ |
| Which one handles dependency ordering? | Topological Sort ✅ |
# ✅ Final Mental Model
| Topological Sort | Quick Union | |
|---|---|---|
| Graph Type | Directed | Undirected |
| Goal | Respect order, detect cycles | Connect components, detect undirected cycles |
| Typical Problems | Scheduling, compilation order | Kruskal’s MST, dynamic connectivity |