- Let us say you reader work as a match-maker
- And a client complain'd about a deal-breaker.
- "She dated a dear friend before" was what he said,
- "I'd find it most abhor if we had shared a bed.
- Not known to my social circle make sure she be,
- Or by god, this bad-buck business I'll rate shabby."
- A problem like this one dear ol' Kosaraju
- Tried to solve. But was it more than what he could chew?
- Fear not, for foresight sleekly set him out to find
- An algorithm so neat; a one-of-a-kind.
- One that runs linearly in time and in space,
- Designed neatly to be speedy and full of grace.
- You must interpret first people as a network
- Where Bob connects to Alice if he was a jerk,
- or a lover, or simply in acknowledgement.
- Then comsume one strongly connected component
- That clearly does not include your careful client
- And pick potentials from that pool to be compliant.
- But how do you go about finding a strongly
- Connected component from a graph so quickly?
- Precisely that process Kosaraju and kin
- Published the year after nineteen seventy sev'n.
- Let list L from holding elements be acquit,
- First step is to set all vertices to-visit.
- Then one by one through the vertices you should loop
- And view each as visited, and its neighbors group
- To recurse on them after in L they'd instill
- If the vertex was marked to-visit, else nil.
- When pushing the neighbors be certain to prepend
- Cause the next step will crucially on it depend:
- To go in twine in the L-defined-order 'long
- The vertices and assign each itself belong.
- Where assignment is defined being twixt two nodes
- For former in the latter's assignment it abodes
- And its neighbors' assignment's nest in the latter
- If the former is assigned, else nil's the matter.
- For your match-making mess mister reader rummage
- Through those client-unassigned to avoid damage.