题目：AT_abc_260_f
题意
-
有一个 \(S + T\) 个点 \(m\) 条边的简单无向图 \(G\)。点集 \(V1\) 包括点 \(1 - S\)，点集 \(V2\) 包括点 \(S + 1-S + T\)，同点集的点没有边相连，请输出一个按任意顺序输出任意长度为 \(4\) 的简单环。
-
数据范围：\(2 \le S \le 3 \times 10^5, 2≤T≤3000，4≤M≤min(S×T,3×10^5)\)。
思路
-
因为同点集的点不会连边，所以这 \(4\) 个点所属点集一定为 \(V1,V2,V1,V2\)，所以只要有两个属于 \(V1\) 点 \(x,y\), 都与 \(V2\) 中的 \(u,v\) 两个点有连边，那么这 \(x,y,u,v\) 就构成了一个简单环。
-
那么怎么实现呢？令 \(c_{u,v}\) 表示有 \(c_{u,v}\) 个点与 \(u,v\) 都相连，那么如果有 \(c_{u,v} > 1\) 那么说明有两个属于 \(V1\) 的点与 \(u,v\) 都相连。
-
所以令 \(a_{u,v}\) 表示与 \(u,v\) 都相连的那个点，我们可以枚举 \(S\) 中的每个点，在枚举和当前点 \(x\) 相连的不同的两个点 \(u,v\)，如果 \(a_{u,v} = 0\)，\(a_{u,v} = x\)，否则那么 \(x\) 和 \(a_{u,v}\) 都与 \(u,v\) 相连，\(x,a_{u,v},u,v\) 构成了简单环。
-
但是问题又来了，时间复杂度是多少，每个在 \(V1\) 的点都枚举与它相连的两个点，似乎会超时。但是实际上你最多枚举 \(T^2\) 个点对，否则就出现重复了（抽屉原理），直接输出，结束程序即可。
-
时间复杂度：\(O(S + T^2)\)