Longest Chain of Loop Clubs — Solution & Editorial

Back to the Problem

Inside an SCC a walk collects every node, so condense: the answer is the maximum node-weight path in the condensation DAG, where each super-node weighs its SCC's size — a topological-order DP.

Complexity: O(N + M)

Watch out: The condensation may contain parallel edges — dedupe or the DP revisits neighbours.