B. Fish Graph(dfs找环)

Problem - 1817B - Codeforces

给定一个具有n个节点和m条边的简单无向图。请注意，该图不一定是连通的。节点从1到n标记。

如果图包含具有特殊节点u的简单循环，则定义图为Fish Graph。除循环中的边之外，图应恰好有2条额外的边。两条边都应连接到节点u，但它们不应连接到循环的任何其他节点。

确定图是否包含子图，其中包含Fish图，并且如果是这样，请找到任何此类子图。

在本问题中，我们将子图定义为通过取原始图的任意边集获得的图像。

输入：

第一行输入整数t（1≤t≤1000），表示测试用例数量。接下来是测试用例的描述。

每个测试用例的第一行包含两个整数n和m（1≤n,m≤2000）——节点数和边数。

接下来的m行中的每一行都包含一条边的描述。每行包含两个整数ui和vi（1≤ui,vi≤n，ui≠vi）——一条边连接节点ui到节点vi。

保证没有两条边连接相同的无序节点对。

此外，保证所有测试用例的n总和和m总和均不超过2000。

输出：

对于每个测试用例，如果图包含子图，则输出“YES”，其为Fish图，否则打印“NO”。如果答案是“YES”，则在以下行中输出子图的说明。

说明的第一行包含一个整数k——子图的边数。

在接下来的k行中，输出所选子图的边缘。每个k行都应包含两个整数u和v（1≤u,v≤n，u≠v）——连接u和v的边属于子图。打印u和v的顺序无所谓，只要两个节点由原始图中的一条边连接即可。无论如何打印边缘的顺序都没有关系，只要结果子图是Fish Graph。

如果有多个解决方案，请打印任何一个。

示例：

Example

Input

Copy

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

Copy

题解:
如果有这样的子图,其中一个点度数一定>= 4,一个环上的点外连两条枝干,即使这两条枝干也属于一个环,也没问题,因为我们找的是子图,只要拿特定的边即可

因此我们只需要搜索每个度数>=4的点,看他是否有环,有环就一定是

具体细节代码中都有注释

#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
 #define int long long
typedef pair<int,int> PII;
typedef unsigned long long ULL;
const int N = 4e5 + 10;
int mod = 1e9 + 7;
vector<int> p[N];
vector<int> ans;
int st[N];//看当前点是否走过
int vis[N];//标记目标节点相邻的节点
int dfs(int u,int f)
{
	if(st[u])
	return 0;
	ans.push_back(u);//存点
	st[u] = 1;
	if(vis[u]&&u != f)
	return 1;//如果碰到了,与目标节点相邻的节点,并且不是我们最开始的搜索起点,说明存在环
	for(auto ne:p[u])
	{
		if(dfs(ne,f))
		return 1;
	}
	ans.pop_back();//如果无环清空
	return 0;
}
void solve()
{
	int n,m;
	cin >> n >> m;
	for(int i = 1;i <= m;i++)
	{
		int x,y;
		cin >> x >> y;
		p[x].push_back(y);
		p[y].push_back(x);
	}
	int f = 0;
	ans.clear();
	for(int i = 1;i <= n;i++)
	{
		if(p[i].size() < 4)
		continue;
		for(int j = 1;j <= n;j++)
		{
			st[j] = 0;
			vis[j] = 0;
		}
		st[i] = 1;
		for(auto ne:p[i])
		{
			vis[ne] = 1;
		}
		for(auto ne:p[i])
		{
			if(dfs(ne,ne))
			{
				f = i;
				break;
			}
		}
		if(f)
		break;
	}
	if(f)
	{
		cout <<"YES\n";
		cout << ans.size() + 3 <<"\n";
		cout << f <<" "<<ans[0] <<"\n";
		cout << f <<" "<<ans[ans.size() - 1] <<"\n";
		for(int i = 0;i < ans.size() - 1;i++)
		cout << ans[i] <<" " << ans[i + 1] <<"\n";
		int c = 0;
		for(auto ne:p[f])
		{
			if(c == 2)
			break;
			if(ne != ans[0]&&ne != ans[ans.size() - 1])
			{
				cout <<f <<" " <<ne <<"\n";
				c++;
			}
		}
	}
	else
	{
		cout <<"NO\n";
	}
	
	for(int i = 1;i <= n;i++)
	{
		p[i].clear();
	}
}
signed main()
{
	ios::sync_with_stdio(0 );
	cin.tie(0);cout.tie(0);
	int t = 1;
	cin >> t;
	while(t--)
	{
		solve(); 
	}
}