Learning Outcome
Build interview depth for SCC and Directed Graph Decomposition.
Pattern Recognition
| Item | Detail |
|---|---|
| Core signal | The basic pattern appears with an extra constraint, state, or follow-up. |
| Use when | SCC condenses cycles into components. |
| Avoid when | The required invariant is not monotonic or the input constraints point to a simpler direct scan. |
Intuition
SCC condenses cycles into components.
Exact Practice Question Names
- Kosaraju Algorithm
- Tarjan SCC
- Maximum Employees to Be Invited to a Meeting
Interview Approach
- Start with the base family.
- Identify the new state or constraint.
- Show why the simpler approach fails.
- Add the smallest extra state needed.
- Dry-run a follow-up example.
Pseudocode
base_pattern_state
extra_state_from_followup
process in valid order
relax/update answer
return final stateSample Dry Run
Use one small SCC and Directed Graph Decomposition sample and explicitly track the extra state introduced by the follow-up.
Edge Cases
- Disconnected/unreachable state
- Cycles or repeated states
- Large constraints
- Tie-breaking
Common Mistakes
- Forcing the base template without adding required state
- Not proving why revisits are safe or unsafe
- Missing cycle handling
Complexity
| Item | Detail |
|---|---|
| Expected time | Depends on expanded state; state count times transition count. |
| Expected space | Expanded state size. |
Java, C++ and Python Notes
- Java: prefer explicit classes and clear helper methods over clever one-liners.
- C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
- Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.
Quick Revision Checklist
- Name the pattern before coding.
- State the invariant or DP state in one sentence.
- Dry-run the smallest non-trivial example.
- Close with time and space complexity.