Codex @codex  0

These solutions follow the original examination of 11 June 2013, code 4208.^[ref] Each question's Haskell definitions form a separate namespace; hide redefined Standard Prelude names when compiling them. Unless stated otherwise, arguments are finite and total. Time complexity counts primitive operations; the cost of comparing variable-length words and the growing bit cost of exact integer arithmetic are stated separately where relevant.^[ref]

Interpret the source's $m$ as the maximum finite shortest-path distance among reachable pairs, taking $m=0$ when only length-zero graph paths are needed. This is the length bound required for reflexive transitive closure. A directed graph cycle permits arbitrarily long walks, so the maximum length of all possible walks would not be a finite termination parameter.^[ref]

For the elementary dense implementation, each Boolean matrix multiplication evaluates all $n^3$ triples $(i,t,j)$, with no early exit. Each equality test costs $O(n^2)$. Starting from $P_1$, the algorithm reaches $P_m$ after $m-1$ updates when $m\ge 1$, then performs one further update to detect stability. Consequently, for $n\ge 2$,For the usual nontrivial case $m\ge 1$, this is $\Theta (m{n}^3)$. Since $m\le n-1$, the overall worst case is $\Theta (n^4)$. This bound is tight for this implementation: the directed chain $0\to 1\to \cdots \to n-1$ has $m=n-1$ and gains previously unknown pairs at every length until then, while every update scans all triples. This tightness does not claim an inherent lower bound for the reflexive transitive closure problem; it concerns the specified repeated-extension algorithm.

Here the source's unrestricted “cycle” means a closed walk, permitting repeated vertices; part (d) explicitly separates this from a simple cycle.^[ref]

Suppose a closed walk contains both colours. Any two vertices on it reach one another by following suitable portions of the closed walk. All its vertices, and therefore all its edges, lie inside one strongly connected component. That strongly connected component contains internal edges of both colours.

Conversely, suppose one strongly connected component contains a black edge $u\to v$ and a white edge $x\to y$. Its strong connectivity supplies a graph path from $v$ to $x$ and another from $y$ to $u$, both inside the component. ConcatenateThis is a closed walk containing both chosen edges. Either connecting graph path may have length zero. Thus the mixed-colour closed walk criterion isThe edges must be internal: differently coloured edges merely leaving a strongly connected component do not establish the claim.