[LOJ 3077] Poem

Difficulty Ratings

Idea Creativity: 4/5
Techniques Used: 3/5
Implementation : 3/5

Link

Simplified Chinese by zhangzy

Statement

Given an undirected graph with $n \le 1e4$ vertices and $m \le 1e6 edges$, determine if there are two simple cycles of same size in the graph.

Solution

We will exhausive search for all cycle lengths for every edge biconnected component sepeartely. Now assume the graph is edge-biconnected.

According to RMM 2019 Q3, when $M-N>c \sqrt{NlgN}$ for some constant $c$, the answer must be Yes. (By instinct if $M-N$ is big it would obviously fail, so you can just guess this $M-N>magic$ and put the largest $magic$ that your solution can run in time.)

Now, we build a condensed graph by repeatedly contracting nodes of degree $2$. As there are no degree 1 vertices (the graph is biconnected), the graph we have now has both $|V|$ and $|E|$ in $O(\sqrt{NlgN})$.

Consider we run an exhausive search for all cycles. We pick a vertex and assume that the cycle includes it. Then we brute force the next neighbour. Each cycle would be found exactly twice. Then, we remove the vertex and search on new graph.

Assume we are in a step of the exhaustion. We firstly temporarily remove the lastest element added to the cycle (so all members in the current part of the cycles are removed), then we build BCC on the current graph in $O(V+E)$. Then we know that for some neighbours of the latest element, if we pick it to be the next element of the cycle, it is guarenteed that at least one cycle could be found; and for the other neighbours, we wont find a cycle if we pick it as next element so we can ignore. Therefore, in each state that you visit, it is guarenteed that there is at least one way to complete this cycle.

As you would find $O(N)$ cycle at most (or you would find two cycles of same length and terminate immediately), each cycle has $O(V)$ edges in condensed graph, you would visit $O(NV)$ states only. And in each state, you do BCC once, which costs $O(E)$, so the total complexity is $O(NVE) = O(N^2lgN)$, and will pass since $c$ is small.

Comments

I think the fact that you can brute force search all cycles in the graph is very cool. Also, data is very hard to construct in this problem, so it is also "interesting" in some sense if you can pass bad and wrong solutions in this task :P.