Official

F - Find 4-cycle Editorial by en_translator

This problem requires a kind of ad-hoc ideas. Some of you may come up with the answer with a couple of hints, so let us reveal them one by one.

Hint 1 There are $\mathrm{O}(T^2)$ pairs of vertices in $V_2$, where $T^2 \simeq 10^7$ is sufficiently small.

Hint 2 Suppose that, for a pair $(x,y)$ of vertices in $V_2$, we found two vertices in $V_1$ which are adjacent to both $x$ and $y$. (Let $z$ and $w$ be these vertices.) Then, $(x, y, z, w)$ forms a 4-cycle. The key is that "all we need is such two vertices."

Hint 3 We can construct a fast algorithm based on Hint 1 and 2 as well as a mathematical idea ...

Hint 4 which is called "the Pigeonhole Principle."

Solution The problem can be solved with the algorithm described by the following procedure.

  • Store the edges of $G$ in an adjacency list $L$ where the indices correspond to the vertices in $V_1$ and the elements in the list to those in $V_2$.
  • Prepare a $T \times T$ two-dimensional array $M$ whose indices correspond to the vertices in $V_2$. The elements of $M$ are all initialized with $M$.
  • For each $z \in V_1$, scan $L[z]$ (that is, the list of vertices adjacent to $z$) with a double for-loop like for x in L[z]: for y in L[z]:.
  • In the for loop, do the following:
    • If $x=y$, then continue without doing anything.
    • If $x \neq y$, do one of the following depending on $M[x][y]$.
      • If $M[x][y]$ equals $-1$, then it means that we have not found a vertex adjacent to $x$ and $y$ yet, so let $M[x][y] = z$ and continue.
      • If $M[x][y]$ does not equal $-1$, then let $w = M[x][y]$. $w$ is a vertex adjacent to both $x$ and $y$. Thus, $x,y,z$, and $w$ form a 4-cycle, so print them and terminate the program.
  • If a 4-cycle wasn't found after scanning all $z$, print -1 and terminate the program.
The algorithm can be justified because we can assert that any cycle is detected by it.
Let us consider the complexity, which depends on the number of tuples of vertices $(z, x, y)$ enumerated by the innermost loop. Let us proof by exhaustion: $x=y$ and $x \neq y$.
The number of tuples such that $x=y$ is bounded by the number of vertex pairs $(z, x)$ where there is an edge between $z-x$, which in turn is bounded by the number of edges $M$.
That of $x \new y$ can be bounded by $T(T-1)+1$ using the Pigeonhole Principle: since the array $M$ has $T(T-1)$ elements with $x\neq y$, and the program terminates once it accesses the same element twice, by the Pigeonhole Principle, by the time $(z,x,y)$ are enumerated $T(T-1)+1$ times, there are at least one element accessed twice and the program terminates.
Therefore, the problem has been solved in a total of $\mathrm{O}(S+M+T^2)$ time.

posted:
last update: