D. Fish Graph
You are given a simple undirected graph with $n$ nodes and $m$ edges. Note that the graph is not necessarily connected. The nodes are labeled from $1$ to $n$.
We define a graph to be a Fish Graph if it contains a simple cycle with a special node $u$ belonging to the cycle. Apart from the edges in the cycle, the graph should have exactly $2$ extra edges. Both edges should connect to node $u$, but they should not be connected to any other node of the cycle.
Determine if the graph contains a subgraph that is a Fish Graph, and if so, find any such subgraph.
In this problem, we define a subgraph as a graph obtained by taking any subset of the edges of the original graph.
Visualization of example 1. The red edges form one possible subgraph that is a Fish Graph.
Input
The first line of input contains the integer $t$ ($1 \leq t \leq 1000$), the number of test cases. The description of test cases follows.
The first line of each test case contains two integers, $n$ and $m$ ($1 \le n, m \le 2\,000$) — the number of nodes and the number of edges.
Each of the next $m$ lines contains the description of an edge. Each line contains two integers $u_i$ and $v_i$ ($1 \leq u_i, v_i \leq n$, $u_i\neq v_i$) — an edge connects node $u_i$ to node $v_i$.
It is guaranteed that no two edges connect the same unordered pair of nodes.
Furthermore, it is guaranteed that the sum of $n$ and the sum of $m$ over all test cases both do not exceed $2\,000$.
Output
For each testcase, output "YES" if the graph contains a subgraph that is a Fish Graph, otherwise print "NO". If the answer is "YES", on the following lines output a description of the subgraph.
The first line of the description contains one integer $k$ — the number of edges of the subgraph.
On the next $k$ lines, output the edges of the chosen subgraph. Each of the $k$ lines should contains two integers $u$ and $v$ ($1\le u, v\le n$, $u\neq v$) — the edge between $u$ and $v$ belongs to the subgraph. The order in which $u$ and $v$ are printed does not matter, as long as the two nodes are connected by an edge in the original graph. The order in which you print the edges does not matter, as long as the resulting subgraph is a fish graph.
If there are multiple solutions, print any.
Example
input
3 7 8 1 2 2 3 3 4 4 1 4 5 4 6 4 2 6 7 7 7 6 7 1 2 2 3 3 4 4 1 1 3 3 5 4 4 1 3 3 4 4 1 1 2
output
YES 6 5 4 6 4 4 3 1 4 2 1 3 2 YES 5 5 3 2 3 3 1 4 3 1 4 NO
Note
In the first example, a possible valid subgraph contains the cycle $1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$. The special node of this cycle is node $4$. The two extra edges $4 - 5$ and $4 - 6$ are both connected to $4$, completing the Fish Graph.
In the second example, a possible valid subgraph contains the cycle $1 \rightarrow 3 \rightarrow 4 \rightarrow 1$. The special node of this cycle is node $3$. The two extra edges $3 - 2$ and $3 - 5$ are both connected to $3$, completing the Fish Graph.
In the last example, it can be proven that there is no valid subgraph.
解题思路
首先可以想到枚举每一个点$u$，把这个点当作鱼图中的特殊点，看看这个点是否满足在某个环内且连着另外两个不在环中的点。因此容易知道如果某个子图是鱼图，那么这个鱼图中的特殊点$u$的度数至少为$4$，其中由于$u$在某个环内因此就贡献了$2$个度数，另外还要再连两个不在环中的点又贡献了$2$个度数，因此至少有$4$个度数。
那么如果某个点的度数至少为$4$能否说明这个点是某个鱼图的特殊点呢？并不能，参考下图：
对于一个度数至少为$4$的点，还应该要满足这个点在某个环内且存在另外两个不在环中直接相连的点，这时才可以判断这个点是某个鱼图的特殊点。
因此现在的问题就变成了给定一个点$u$，如何找到一个$u$所在的环，且还存在两个不在环中的点与$u$相连。然而包含$u$的环可能有非常多，如果直接暴搜来找的话肯定会超时，因此我们尝试去想能不能只找长度最小的环，且使得存在两个不在环中的点。要证明这点，只需证明对于任意一个鱼图，如果$u$不在最小环那么一定可以变成最小环且仍然是鱼图。
假设另外两个直接相连的点$a$和$b$都不在最小环上，那么直接把环变成最小环即可。如果$a$或$b$有一个在最小环上（不失一般性假设为$a$），由于当前环的长度至少要比最小环多$1$，意味着当前环上至少存在一个点不在最小环上，因此这个点可以与$b$作为不在最小环上且与$u$直接相连的点。如果$a$与$b$都在最小环上，那么一定可以在当前环上找到两个不在最小环上的点，否则当前环上的点都在最小环上那么最小环的长度就比当前环的长度多出$2$就矛盾了。
因此对于每个度数大于$4$的节点$u$，枚举所有邻边$(u,v)$，然后把$(u,v)$删掉跑一遍bfs，如果存在从$v$到$u$的路径那么就存在一个$u \to \cdots \to v \to u$的最小环，把在这个环上的所有点都标出来。最后再遍历所有含$u$的边，如果存在至少两个没有被标记的相点，则说明$u$是某个鱼图的特殊点，即存在某个子图是鱼图。
AC代码如下，时间复杂度为$O(m \times (n+m))$：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 2010, M = N * 2;
5
6 int head[N], e[M], ne[M], idx;
7 int deg[N];
8 int q[N], dist[N], p[N];
9 bool vis[N];
10
11 void add(int v, int w) {
12 e[idx] = w, ne[idx] = head[v], head[v] = idx++;
13 }
14
15 void solve() {
16 int n, m;
17 scanf("%d %d", &n, &m);
18 idx = 0;
19 memset(head, -1, sizeof(head));
20 memset(deg, 0, sizeof(deg));
21 while (m--) {
22 int v, w;
23 scanf("%d %d", &v, &w);
24 add(v, w), add(w, v);
25 deg[v]++, deg[w]++;
26 }
27 for (int i = 1; i <= n; i++) {
28 if (deg[i] >= 4) { // 只有度数至少为4的点才有可能是鱼图的特殊点
29 for (int j = head[i]; j != -1; j = ne[j]) { // 枚举所有的边，删去这条边跑bfs
30 memset(dist, 0x3f, sizeof(dist));
31 dist[i] = 0;
32 int hh = 0, tt = -1;
33 q[++tt] = i;
34 memset(p, 0, sizeof(p));
35 while (hh <= tt) {
36 int t = q[hh++];
37 for (int k = head[t]; k != -1; k = ne[k]) {
38 if (t == i && e[k] == e[j] || t == e[j] && e[k] == i) continue; // 跳过删除的边
39 if (dist[e[k]] > dist[t] + 1) {
40 dist[e[k]] = dist[t] + 1;
41 p[e[k]] = t; // 记录从哪个点转移过来的
42 q[++tt] = e[k];
43 }
44 }
45 }
46 if (dist[e[j]] < 0x3f3f3f3f) { // 存在从i到e[j]的路径，说明存在环
47 memset(vis, 0, sizeof(vis));
48 int t = e[j];
49 vector<vector<int>> ans({{i, e[j]}});
50 while (p[t]) { // 把环上所有点标出来
51 vis[t] = true;
52 ans.push_back({t, p[t]});
53 t = p[t];
54 }
55 int cnt = 2; // 找两个不在环上的点
56 for (int k = head[i]; k != -1; k = ne[k]) {
57 if (!vis[e[k]]) {
58 ans.push_back({i, e[k]});
59 if (--cnt == 0) break;
60 }
61 }
62 if (!cnt) { // 存在环且存在两个不在环上的点，则存在鱼图
63 printf("YES\n%d\n", ans.size());
64 for (auto &p : ans) {
65 printf("%d %d\n", p[0], p[1]);
66 }
67 return;
68 }
69 }
70 }
71 }
72 }
73 printf("NO\n");
74 }
75
76 int main() {
77 int t;
78 scanf("%d", &t);
79 while (t--) {
80 solve();
81 }
82
83 return 0;
84 }
参考资料
Codeforces Round #869 (Div.1, Div.2) Editorial：https://codeforces.com/blog/entry/115586
标签：环上,subgraph,int,Graph,Fish,contains,鱼图,edges From： https://www.cnblogs.com/onlyblues/p/17378382.html