How would you check strong connectivity of a ten-million-page crawl link graph in linear time?

## Separate the question from the decomposition "Can every page reach every other page?" is a single boolean. Computing all strongly connected components answers it — there is exactly one component if and only if the graph is strongly connected — but that is more machinery than the question needs, and at ten million pages the difference in memory and passes is real. The cheap test uses a root and a symmetry argument. Pick any vertex `r`. 1. **Forward sweep.** Traverse from `r` following links in their natural direction. If it visits fewer than V pages, some page is unreachable from `r`: not strongly connected, and you already have a witness. 2. **Backward sweep.** Traverse from `r` following links in reverse. If it visits fewer than V pages, some page cannot reach `r`: again not strongly connected. 3. **Both cover everything → strongly connected.** For arbitrary `u` and `v`, the backward sweep gives a path `u -> r` and the forward sweep gives `r -> v`; concatenate them for `u -> v`. Swap roles for `v -> u`. Two traversals, each O(V + E). The root can be any vertex; nothing about the choice matters to correctness. ## The costs you are being tested against | approach | cost | verdict | | --- | --- | --- | | traverse from every page | O(V * (V + E)) | hopeless at 10^7 | | transitive closure | O(V^2) space at minimum | 10^14 bits; not a plan | | full component decomposition | O(V + E) | correct, but more than asked | | two-sweep root test | O(V + E), two passes | the answer | The wrong answers here are not exotic — "run a traversal from each page and check it reaches everything" is the reflex, and it multiplies a linear job by ten million. ## What actually bites at this size - **Recursion depth is space.** A recursive traversal's stack depth can reach the vertex count on a long chain of pages, and a crawl graph has plenty of long chains. Convert to an explicit stack or a queue. This is the failure that shows up as a crash rather than as slowness. - **The reverse adjacency has to come from somewhere.** Following links backwards needs the reversed edge list. Either you store both directions — roughly doubling edge memory, and a crawl graph's edges dwarf its vertices — or you rebuild the reverse structure in a separate streaming pass over the edge file, trading a pass for the memory. Which one is right depends on whether edges fit in memory at all. - **Compact representation wins.** Store adjacency as sorted index arrays with an offset table rather than per-vertex link objects, and keep the visited marker as a bit array — one bit per page instead of a pointer per page. - **One sweep is not enough.** Reaching everything from `r` proves only out-reachability. This is the single most common half-answer: it establishes that `r` broadcasts, not that anyone can answer back. - **Weak connectivity is not the answer either.** A crawl graph is almost always weakly connected and almost never strongly connected — most real link graphs have one large mutually reachable core plus large in-only and out-only regions. So expect the answer to be "no", which makes the follow-up the interesting part. ## When the answer is no The useful next question is usually "then how large is the biggest mutually reachable cluster?" — and that genuinely needs the full decomposition, in linear time, using either the two-pass finish-order method or the one-pass low-link method. At this scale the one-pass method's avoidance of a reversed copy is a memory argument worth making, while the two-pass method is easier to verify. Both need the same iterative rewrite for depth. A cheap partial answer also exists: the component containing `r` is exactly the intersection of the forward-reachable set and the backward-reachable set you already computed. That is one component for free out of the two sweeps you have already paid for — often enough to report the size of the core without a full decomposition. ## How to say it in an interview "Strong connectivity is one boolean, so I would not decompose. Pick any page, traverse forward, traverse backward on reversed links; if both cover all pages the graph is strongly connected, because every page reaches the root and the root reaches every page. Two linear sweeps. At ten million pages I would make the traversals iterative — recursion depth can hit the vertex count — use bit-array visited marks, and decide whether to store reversed edges or rebuild them in a pass, since that is the real memory cost. And the intersection of the two reached sets is the root's own component, free."