给出一个无向简单图，判断是否存在两个长度相同的简单环。
第一行包含两个正整数 $n, m$ ($n \leq 10000; m \leq 10^6$)，表示点数和边数。
接下来 $m$ 行，每行两个正整数 $u, v$ ($1 \leq u, v \leq n; u \neq v$)，描述一条边。
输出一行，包含一个字符串，若存在两个长度相同的简单环，输出 Yes；否则，输出 No。
(注：如上面链接所描述，这里的 "简单环" 指的是不经过重复点的环。)
首先，默认假设图 $G = \left( V, E \right)$ 是连通的，否则，设它由 $k$ 个连通分量构成：$G = G_1 \oplus G_2 \oplus \cdots \oplus G_k$，则在 $G_i$ 中任取一个点 $v_i$，顺次连成一条链 (即连接 $\left( v_1, v_2 \right), \left( v_2, v_3 \right), \cdots, \left( v_{k-1}, v_k \right)$)，则新图 $G'$ 和原图 $G$ 的成环情况相同，于是答案相同。
对连通图 $G$，设 $\beta \left( G \right) = \left| E \left( G \right) \right| - \left| V \left( G \right) \right| + 1$ (组合意义为对于它的任意一棵生成树，非树边的条数)，则有下列定理成立：
设 $M \left( t \right)$ 表示 $\beta \left( G \right) = t$ 且不存在两个长度相同的简单环 (即答案为 No) 的连通无向简单图 $G$ 的阶的最小值，则 $M \left( t \right) = \Theta \left( t^2 \right)$。
关于 $M \left( t \right)$ 的量，目前猜想它的紧确界为 $M \left( t \right) \sim \dfrac {t^2} 2$，但尚未得到证明 (可以理解为一个估计？)。
容易说明 $M \left( t \right) \leq \dfrac {t^2} 2 + O \left( t \right)$，只需要将大小为 $3, 4, 5, \cdots$ 的环拼连接在一起即可。
下面给出 $M \left( t \right) = \Omega \left( t^2 \right)$ 的证明：
设连通无向简单图 $G = \left( V, E \right)$ 中且不存在两个长度相同的简单环。取 $G$ 的一个生成树 $T$，则剩下的边数为 $\beta = \left| E \right| - \left| V \right| + 1$。容易发现，$G$ 至少有 $\beta$ 个环，又环长 $< n$，于是 $\beta < \left| V \right|$。
设 $G_0 = G$ 中有 $cyc_0$ 个环。由于 $G$ 的所有简单环长度互不相同，因此环的总长 $\geq 3 + 4 + \cdots + \left( 2 + cyc_0 \right) > \dfrac {cyc_0^2} 2$。由于 $\left| E \right| = \left| V \right| - 1 + \beta < 2 \left| V \right|$，由抽屉原理，一定存在一条边 $e_0$，它在至少 $\left \lceil \dfrac {cyc_0^2} {4 \left| V \right|} \right \rceil$ 条边上。
令 $G_1 = G_0 \setminus \left\{ e_0 \right\}$。则 $G_1$ 的环数为 $cyc_1 \leq \left \lfloor cyc_0 - \dfrac {cyc_0^2} {4 \left| V \right|} \right \rfloor < cyc_0$。使用同样的规则找到边 $e_1$，并将其删去，得到图 $G_2 = G_1 \setminus \left\{ e_1 \right\}$，同理有 $cyc_2 \leq \left \lfloor cyc_1 - \dfrac {cyc_1^2} {4 \left| V \right|} \right \rfloor$，……，直到所有的环均被删光，即 $cyc_\beta = 0$。
考察数列 $\left\{ cyc_n \right\}_{0 \leq n \leq \beta}$，它满足关系式 $cyc_0 < \left| V \right|, cyc_{i+1} \leq \left \lfloor cyc_i - \dfrac {cyc_i^2} {4 \left| V \right|} \right \rfloor$。
由于 $cyc_n$ 严格递减且最后为 $0$，因此一定存在一个 $\xi$，使得 $cyc_\xi \geq 2 \sqrt {\left| V \right|} \wedge cyc_{\xi + 1} < 2 \sqrt {\left| V \right|}$。
当 $i \geq \xi$ 时，由于 $cyc_{i+1} < cyc_i$，因此 $\beta - \xi \leq 2 \sqrt {\left| V \right|}$。
当 $i < \xi$ 时，由于 $cyc_{i+1} \leq cyc_i - \dfrac {cyc_i^2} {4 \left| V \right|} = cyc_i \cdot \left( 1 - \dfrac {cyc_i} {4 \left| V \right|} \right)$，因此 $\dfrac 1 {cyc_{i+1}} \geq \dfrac 1 {cyc_i} \cdot \dfrac {4 \left| V \right|} {4 \left| V \right| - cyc_i} = \dfrac 1 {cyc_i} \cdot \left( 1 + \dfrac {cyc_i} {4 \left| V \right| - cyc_i} \right) = \dfrac 1 {cyc_i} + \dfrac 1 {4 \left| V \right| - cyc_i} > \dfrac 1 {cyc_i} + \dfrac 1 {4 \left| V \right|}$。
而 $cyc_\xi \geq 2 \sqrt {\left| V \right|} \Rightarrow \dfrac 1 {cyc_\xi} \leq \dfrac 1 {2 \sqrt {\left| V \right|}}$，且 $\dfrac 1 {cyc_0} > 0$，因此 $\xi < \dfrac 1 {2 \sqrt {\left| V \right|}} \cdot 4 \left| V \right| = 2 \sqrt {\left| V \right|}$。
结合两个红色结果，可知：$\beta < 4 \sqrt {\left| V \right|}$，即 $\left| V \right| > \dfrac {\beta^2} {16}$。因此 $M \left( t \right) > \dfrac {t^2} {16}$，由大 $\Theta$ 符号的定义知，$M \left( t \right) = \Theta \left( t^2 \right)$。
这个结论的一个直接推论是：如果一张 $n$ 阶图的 $\beta$ 数大于 $O \left( \sqrt n \right)$ (如果使用上面的猜想，则为 $\sqrt {2 n} + o \left( \sqrt n \right)$)，则这张图一定存在两个长度相同的简单环 (即答案为 Yes) (这个结论在 RMM2019 中也出现过)。
因此以下默认考虑 $\left| E \right| \leq \left| V \right| + \sqrt {2 \left| V \right|} + o \left( \sqrt {\left| V \right|} \right)$ 且图连通的情况。
首先，由简单环的性质，每个简单环一定完整地包含在一个点双连通分量中。
不过由于不同的点双之间会有交集，这会带来少许的麻烦，因此我们减弱条件，利用每个简单环一定完整地包含在一个边双连通分量中的条件，将原图进行边双缩点。
考虑一个非平凡 (即至少 $3$ 个点的) 边双连通分量 $B = \left( V_B, E_B \right)$，显然 $\left| E_B \right| \geq \left| V_B \right|$ (必然是连通图且不是树)。如果 $\left| E_B \right| \geq \left| V_B \right| + \sqrt {2 \left| V_B \right|} + o \left( \sqrt {\left| V_B \right|} \right)$，则由上面的结论，$B$ 内部一定存在两个长度相同的简单环。因此下面只讨论 $\left| V_B \right| \leq \left| E_B \right| \leq \left| V_B \right| + \sqrt {2 \left| V_B \right|} + o \left( \sqrt {\left| V_B \right|} \right)$ 的情况。
注意到 $B$ 中每个点的度数均 $\geq 2$，因此由握手定理 (这里的式 $\left( 1 \right)$)，度数超过 $2$ 的点的个数是 $O \left( \sqrt {\left| V_B \right|} \right)$ 的。
考虑对 $B$ 中每个 $2$ 度点，我们可以将其进行缩点操作 (即对于 $N \left( u \right) = \left\{ x, y \right\}$，删去点 $u$ 和边 $\left( x, u \right), \left( u, y \right)$，连接 $\left( x, y \right)$)，则最后缩点后得到的图 $B' = \left( V', E' \right)$ 满足 $\left| V' \right|, \left| E' \right| = O \left( \sqrt {\left| V_B \right|} \right)$，说白了就是一个不超过 $200$ 个点的图。
最后我们所要做的，就是暴力枚举这张图 $B'$ 上的所有环，检验是否有两个的长度相同。
不过这里要注意的是，由于环是无序的，因此根据套路，我们需要枚举环中编号最小的节点 $v$ (即让路径上的所有节点的编号都 $\geq v$)。
这样一来，由于正、反的因素，每个环会被搜到 $2$ 遍。因此，如果对于一个长度，它出现了至少 $3$ 次，则可以断定答案是 Yes 了。
然后等你把暴力写完，发现 TLE 了。
你对一张百来个点的图进行暴力 dfs 还想过？
这是因为，尽管 $B'$ 环的数量并不是很多，但并不是每一次搜索都是奔着环去搜的。因为对于这种类型的图，很多情况下，你搜了很小一部分后，后面就一定无解了——因此我们需要做的就是剪枝。
在 dfs 的过程中，每进行若干步 (一步或多步)，就进行一次可行性检验——即检验只走剩下的边，能否形成一个环。也就是说，将已经走过的点和边删去，检验当前点和 $v$ (枚举的最小点) 是否还连通。
这样时间复杂度就正确了。因为环的数量不超过 $n$ (因为一旦搜到超过 $n$，则可以直接输出 Yes)，(缩点后) 环长是 $O \left( \sqrt n \right)$ 的，判断连通性 (可以使用并查集、bfs 等) 的时间复杂度也是 $O \left( \sqrt n \right)$，因此总时间复杂度就是 $O \left( n^2 \right)$ (别慌，$O \left( n^2 \right)$ 过 $10000$ 是一个再常见不过的事情)。
#include <bits/stdc++.h>
#define EB emplace_back
#define ad(x) ((((x) - 1) ^ 1) + 1)
typedef long long ll;
const int N = 10054, M = 2000054;
struct edge {
int u, v, w;
edge (int u0 = 0, int v0 = 0, int w0 = 1) : u(u0), v(v0), w(w0) {}
} e[M], ee[M];
int V, E, Es = 0;
int first[N], next[M], deg[N];
int cnt = 0, id[N], low[N];
int top = 0, stack[N], bel[N];
int Vsize[N], Esize[N], cyc[N];
int tcnt = 0, turn[N];
bool filled[N], used[N], eused[N];
inline void down(int &x, const int y) {x > y ? x = y : 0;}
inline ll limit(int e) {return e <= 0 ? 0 : e * (e + 1ll) / 2 + 1;}
inline void addedge(int u, int id) {next[id] = first[u], first[u] = id;}
void dfs(int x, int px = 0) {
int i, y;
id[x] = low[x] = ++cnt, stack[top++] = x;
for (i = first[x]; i; i = next[i])
if (!id[y = e[i].v])
dfs(y, i), down(low[x], low[y]);
else if ((px - 1) ^ (i - 1) ^ 1)
down(low[x], low[y]);
if (id[x] == low[x])
for (y = 0; y != x; y = stack[--top], bel[y] = x, ++Vsize[x]);
}
int p[N];
inline int ancestor(int x) {return p[x] == x ? x : (p[x] = ancestor(p[x]));}
inline bool check_connectivity(int st, int x) {
int i;
for (i = 1; i <= tcnt; ++i) if (!used[turn[i]]) p[turn[i]] = turn[i];
for (i = 1; i <= Es; i += 2) if (!eused[i] && !used[ee[i].u] && !used[ee[i].v])
p[ancestor(ee[i].u)] = ancestor(ee[i].v);
return ancestor(x) == ancestor(st);
}
bool dfs2(int x, int st, int len) {
int i, y;
if (x == st && len) return ++cyc[len] > 2;
for (i = first[x]; i; i = next[i])
if (!eused[i] && !used[y = ee[i].v]) {
eused[i] = eused[ad(i)] = true;
if (check_connectivity(st, y)) {
used[y] = true;
if (dfs2(y, st, len + ee[i].w)) return true;
used[y] = false;
}
eused[i] = eused[ad(i)] = false;
}
return false;
}
int main() {
int i, u, v, bu, bv, len;
scanf("%d%d", &V, &E);
if (V <= limit(E - V + 1)) return puts("Yes"), 0;
for (i = 1; i <= E * 2; i += 2)
scanf("%d%d", &u, &v), e[i] = edge(u, v), e[i + 1] = edge(v, u), addedge(u, i), addedge(v, i + 1);
for (i = 1; i <= V; ++i) if (!id[i]) dfs(i);
memset(first, 0, (V + 1) << 2);
for (i = 1; i <= E * 2; i += 2) if (bel[u = e[i].u] == bel[v = e[i].v])
++Esize[bel[u]], ++deg[u], ++deg[v], addedge(u, i), addedge(v, i + 1);
for (i = 1; i <= V; ++i) if (bel[i] == i && Vsize[i] <= limit(Esize[i] - Vsize[i] + 1)) return puts("Yes"), 0;
for (i = 1; i <= E * 2; i += 2) if (bel[u = e[i].u] == bel[v = e[i].v] && deg[u] >= 3 && deg[v] >= 3)
ee[++Es] = edge(u, v, 1), ee[++Es] = edge(v, u, 1);
for (i = 1; i <= V; ++i)
if (deg[i] == 2 && !filled[i]) {
bu = bv = i, len = 2, filled[i] = true;
u = e[first[i]].v, v = e[next[first[i]]].v;
for (; deg[u] == 2 && u != v; std::swap(u, bu), ++len)
filled[u] = true, bu = e[e[first[u]].v == bu ? next[first[u]] : first[u]].v;
if (u == v) {if (filled[u] = true, (cyc[len] += 2) > 2) return puts("Yes"), 0; continue;}
for (; deg[v] == 2 && u != v; std::swap(v, bv), ++len)
filled[v] = true, bv = e[e[first[v]].v == bv ? next[first[v]] : first[v]].v;
if (u == v) {if (filled[v] = true, (cyc[len] += 2) > 2) return puts("Yes"), 0; continue;}
ee[++Es] = edge(u, v, len), ee[++Es] = edge(v, u, len);
}
memset(first, 0, (V + 1) << 2);
for (i = 1; i <= Es; ++i) addedge(ee[i].u, i);
for (i = V; i; --i) if (deg[i] >= 3) turn[++tcnt] = i;
for (i = 1; tcnt; --tcnt) {
for (; i < turn[tcnt]; ++i) used[i] = true;
if (dfs2(turn[tcnt], turn[tcnt], 0)) return puts("Yes"), 0;
}
return puts("No"), 0;
}
坑1：在缩点的过程中，注意一种特殊的情况——即一个边双是一个单环。此时如果不停地找 $2$ 度点将会永无休止地找下去。因此如果发现又遇到了已经找过的点，则说明这里就是一个单环，直接统计贡献即可。
坑2：在用并查集判断连通性的时候，只能对两端都没用过且编号 $\geq v$ 的边进行 union。