Graph Theory37 sections · 1633 units
Open in Course

Chain Heads

(Top node of each chain)

Let head[v] be the topmost node in the chain containing vv. For the node that starts a chain, head[v] = v. For other nodes in the chain, head[v] equals the head of the parent. You compute this during the decomposition DFS. When you start a new chain at node vv, set head[v] = v.

When you extend a chain to child uu via a heavy edge, set head[u] = head[v]. Chain heads help you identify when two nodes are in the same chain: they are in the same chain if and only if they have the same head.