AtCoder Beginner Contest 260 F - Find 4-cycle如何寻找四个元素构成循环？

本文共计592个文字，预计阅读时间需要3分钟。

这是伪造的摘要。题目传送门：atcoder.jp题目：寻找4-环（Find 4-cycle）

题目内容：给定一个无向图，其中包含两个独立的点集S和T（即S、T内部任意两点之间不存在边），再给出图中的M条边（S中的点与T中的点之间的边），要求找出图中是否存在一个4-环（即包含四个顶点的环，且这四个顶点中至少有两个顶点分别属于S和T）。

This is a fake summary.

题目传送门：F - Find 4-cycle (atcoder.jp)

题意：

给定一个无向图，其包含了S、T两个独立点集（即S、T内部间的任意两点之间不存在边），再给出图中的M条边（S中的点与T中的点之间的边）。

求图中包含的一个四元环，若存在则输出环中包含的顶点，否则输出-1。

思路：

首先，四元环只能是由两个S中的点和两个T中的点构成，记为a、b，u、v，且a、b与u、v都直接有边相连。

|S| 为 300000，|T| 为 3000。于是我们考虑枚举S中点，记为Si，再枚举与Si相连的两个不同的点，记为u、v，则我们仍需找到S中一个点（四元环的第四个点，记为Sj），要求其与u、v相连。