CF1817B Fish Graph

定义“鱼图”为满足以下条件的无向图：

• 该图包含正好 $1$ 个环，环上有 $1$ 个特殊的结点 $u$，$u$ 除了连在环上的 $2$ 条边外还有正好 $2$ 条边，每一条边连向一个环外的结点（即，若环的大小为 $s$，整个图一共有 $s+2$ 个结点）。

现在给定一个简单无向图，问该图中是否有一个子图为“鱼图”。一个无向图的子图即为原图中删去若干个点和若干条边所形成的图。如果存在，还需要构造出其中任意一个满足要求的子图。

分析

做法 1

暴力找环，对于每个环，遍历其环上的节点，判断该点入度是否大于 $2$，如果满足条件，直接输出剩余边中的两条和环上的边即可。

做法 2

考虑枚举鱼尾和鱼身的交点 $x$，显然，当且仅当该点度数 $d_x \ge 4$ 满足这个条件，问题变为是否成环。

一种很妙的方法：定义一条路径上的节点的路径 $\text{ID}$ $f_t$ 为路径上第一个点的编号，从 $x$ 出发 $\text{bfs}$，如果成环，那么一定有一条边的两个端点 $f_l$ 和 $f_r$ 不同，对于一个点的出边，判断两端是否有不同的编号即可。

由于使用的 $\text{bfs}$，这种方法找到的同时还是最小环。

由于要输出答案，使用 $road_u$ 表示到达 $u$ 的节点编号，逆推经过的边即可。

代码（做法 2）

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> PII;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) f -= (ch == '-') * 2;
	for (; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);
	return x * f;
}

const int N = 100010, M = 2 * N;

int h[N], e[M], ne[M], idx = 1;
int d[N], f[N], road[N];
vector<PII> ans;

void add(int a, int b) {
	e[ ++ idx] = b, ne[idx] = h[a], h[a] = idx;
}

bool bfs(int st) {
	memset(f, 0, sizeof f);
	memset(road, 0, sizeof road);
	queue<int> q;
	road[st] = -1;
	for (int i = h[st]; i; i = ne[i]) road[e[i]] = st, q.push(f[e[i]] = e[i]);
	while (q.size()) {
		auto u = q.front(); q.pop();
		for (int i = h[u]; i; i = ne[i]) {
			int l = u, r = e[i];
			if (road[r]) {
				if (f[l] == f[r] || r == st) continue;
				int tl = l, tr = r, cnt = 0;
				ans.emplace_back(l, r);
				for (; tl != st; tl = road[tl]) ans.emplace_back(tl, road[tl]);
				for (; tr != st; tr = road[tr]) ans.emplace_back(tr, road[tr]);
				for (int k = h[st]; k; k = ne[k]) {
					int hyl = e[k];
					if (hyl != f[l] && hyl != f[r]) cnt ++ , ans.emplace_back(st, hyl);
					if (cnt == 2) return true;
				}
			}
			road[r] = l, f[r] = f[l];
			q.push(r);
		}
	}
	return false;
}

int main() {
	int _ = read();
	while (_ -- ) {
		ans.clear();
		memset(h, 0, sizeof h);
		memset(d, 0, sizeof d);
		idx = 1;
		int n = read(), m = read();
		for (int i = 1; i <= m; i ++ ) {
			int a = read(), b = read();
			add(a, b), add(b, a);
			d[a] ++ , d[b] ++ ;
		}
		bool check = false;
		for (int i = 1; i <= n; i ++ ) {
			if (d[i] >= 4) {
				check = bfs(i);
				if (check) {
					puts("YES");
					printf("%d\n", ans.size());
					for (int j = 0; j < ans.size(); j ++ ) printf("%d %d\n", ans[j].first, ans[j].second);
					break;
				}
			}
		}
		if (!check) puts("NO");
	}
	return 0;
}

ABC077D Small Multiple