Graph Patterns

Graphs have six algorithm templates (all spelled out in §3 below) but only one setup step — and that setup is where most interview time is actually lost…

Iterate every cell. When you hit unvisited '1', run DFS/BFS to "sink" all connected '1's into '0's and increment a counter.

A directed graph has a valid order iff it has no cycle. Kahn's algorithm processes nodes whose in-degree is 0; if all nodes get processed, the graph is…

Count connected components in an undirected graph given as an adjacency matrix. Each "province" is one component.

Find the shortest delay from source k to every other node. The "delay" of the whole network is the maximum shortest delay among all reachable nodes. If any…

Add edges one by one. The first edge whose two endpoints are already in the same Union-Find component is the redundant one.

All initially rotten oranges spread their rot at the same time. Push every rotten cell into the BFS queue at once, then do level-order BFS — each level = 1…

Same as LC 207, but instead of just true/false, return one valid topological ordering. If a cycle exists, return an empty array.