DSA Sheet - Day 28 Graphs
🌐 DSA Sheet – Day 28: Advanced Graph Patterns
This section focuses on high-level graph concepts like SCC, DSU, bipartite graphs, and advanced applications of traversal and topological sorting.
📊 Progress Tracker
Progress: 0 / 7 Completed
| Done | Problem | Practice | Level | Companies |
|---|---|---|---|---|
| Number of Islands | Solve | Medium | Amazon, Microsoft | |
| Is Graph Bipartite? | Solve | Medium | Uber, Flipkart | |
| Strongly Connected Components (Kosaraju) | Solve | Hard | Paytm | |
| Most Stones Removed | Solve | Medium | Google, Amazon | |
| Number of Ways to Arrive at Destination | Solve | Medium | Amazon, Google | |
| Number of Provinces | Solve | Medium | Google, Amazon | |
| Alien Dictionary | Solve | Hard |
🧠 Key Approaches
- Number of Islands: DFS/BFS on grid
- Bipartite Graph: 2-coloring using BFS/DFS
- Kosaraju: DFS + reverse graph + DFS
- Most Stones: DSU (Union-Find)
- Ways to Destination: Dijkstra + path counting
- Provinces: Connected components
- Alien Dictionary: Build graph + topological sort
⚡ Quick Cheatsheet
Bipartite Graph (Coloring)
color[node] = 0 or 1;
// assign alternate colors to neighbors
Kosaraju Algorithm
// 1. DFS and store nodes in stack
// 2. Reverse graph
// 3. DFS in stack order
Alien Dictionary
// build graph from adjacent words
// apply topological sort
🔥 Pro Tip
Recognize patterns instantly:
- Groups / components? → DFS / BFS / DSU
- 2-group division? → Bipartite (coloring)
- Strong connectivity? → Kosaraju
- Ordering from constraints? → Topological Sort