Data Check

Construct the dual graph $D$ whose vertices are the faces of the grid. There are $(N-1)(M-1)$ inner faces, and the entire exterior of the grid is treated as one outer face.

For a directed primal edge $e$, let $R(e)$ and $L(e)$ be the faces on its right and left when looking along the direction of $e$. Add the following dual edge:

$$R(e) \to L(e).$$

Compute the strongly connected components of $D$ and consider its condensation DAG.

Lemma 1. Inside every directed primal cycle, there is a source SCC or a sink SCC that does not contain the outer face.

For a clockwise cycle, its interior lies on the right of every edge. Hence every dual edge crossing the cycle goes from the interior to the exterior. A source among the SCCs inside the cycle is therefore also a source in the whole condensation DAG.

For a counterclockwise cycle, every crossing dual edge goes from the exterior to the interior. A sink among the SCCs inside the cycle works instead.

Lemma 2. The outer boundary of every source SCC or sink SCC not containing the outer face contains a directed primal cycle.

A source SCC has no incoming dual edge from another SCC. Thus all dual edges crossing its boundary are directed consistently from the SCC to the outside. Since every dual edge was directed from the right face to the left face, the corresponding primal boundary is directed consistently and forms a directed cycle. The sink case is identical with the direction reversed.

Suppose the rows of the inner faces in an SCC range from $a$ to $b$, and their columns range from $c$ to $d$, using zero-based face coordinates. The minimum vertex rectangle containing its outer boundary is

$$(a+1,c+1,b+2,d+2),$$

with area $(b-a+2)(d-c+2)$.

By Lemma 2, every candidate rectangle really contains a directed cycle. Conversely, applying Lemma 1 to any directed cycle gives a candidate SCC whose rectangle lies inside the cycle's rectangle. Therefore it is sufficient to compare the bounding rectangles of all source and sink SCCs except the SCC containing the outer face.

The number of faces can be about $2.5 \cdot 10^7$, so ordinary adjacency lists use too much memory. The four neighbors of an inner face can be generated directly from $H$ and $V$. Only the dual edges incident to the outer face are stored separately, and iterative Kosaraju is run on this implicit graph.

The time complexity is $O(NM)$ and the memory complexity is $O(NM)$.

Solution written by GPT5.6