#创作计划#AT_abc472_e怎么做

题目意思

给定一个有 $n$ 个点和 $m$ 条边的简单无向图（无重边和自环），若有长度为奇数的环，则输出任意奇环的成员，否则输出 -1 。

错误思路

看到环的那一刻，我想起了拓扑排序，但是这是无向图，且在复杂的图中拓扑排序没有前途。

这张图中拓扑排序在开始就结束了，仅能证明有环，而且在无向图中非常艰难。

正解

这种题是 DFS 奇环检测的模板题。

算法思路

1.在图中随便找一棵树。

2.对树进行二分图染色。

3.寻找是否有连接同色点的边，并根据题目要求解题。在该题中要储存这个环的成员并输出。

思路上可能有的问题

为什么连接同色点的边就会有奇环？

1.对于有一棵有 $num$ 个点的树，有 $num-1$ 条边。若再增加一条边则必然产生环。

2.对于一个环，进行二分图染色，两色交替出现，代表已染色的点数奇偶性在改变，与起点颜色相同则是奇数点数，反之则是偶数点数。当两同色点相邻，则相当于起点与终点颜色相同环的成员数为奇数。

如图所示。

绿色代表建树是连接的边，图中进行的是红黑染色，蓝实线是可选择的奇环添加的边，蓝虚线表示理论上可以但题目未给出的边。

存不存在要连接两个或多个边才会出现奇环的情况？

存在，但不考虑，因为我们只求任意一个奇环，以上情况必然会有一条连接同色点的边，只要有这条边就能找到奇环，不再需要其他边。若没有连接同色点的边，则剩下的边只能组成偶环或者根本没有环。这就是我们只考虑连接一条边的原因。

在代码中如何实现？

染色和建树可以在同一个 DFS 中完成。

我们可以在建树和染色的同时，判断有没有连接同色点的边。并用栈存放。

如图在 DFS 形成的绿色长链上，到了像蓝色符合条件连接链的边，那么就可以用 vector 倒退存储栈中内容，直到存到图中的节点2停下。

细节见以下代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+2;
int n,m;
int c[MAXN];//01二分图染色，若没染色则为-1
vector<int>g[MAXN];//建边
vector<int> ans,pa;//ans存储答案，pa临时存储访问的点（为防止栈溢出，我用vector模拟）
bool f;//f为found缩写，是否找到答案
void dfs(int u,int so){//so表示u应该的颜色或u的父亲节点的相反颜色
	if(c[u]==-1){
		c[u]=so;//染色
		pa.push_back(u);//缓存节点
		for(int v:g[u]){
			if(v==u)continue;
			dfs(v,so^1);
			if(f)return;
		}
		pa.pop_back();//删除节点
	}
	else{
		if(c[u]==so||f)return;
        //找到连接同色点的边
		f=1;
		for(int i=pa.size()-1;i>=0;i--){
			ans.push_back(pa[i]);
			if(pa[i]==u)break;
		}
	}
}
void solve(){
	cin>>n>>m;
	ans.clear();
	pa.clear();
	f=0;
	for(int i=1;i<=n;i++){//清除
		c[i]=-1;
		g[i].clear();
	}
	for(int i=1;i<=m;i++){
		int a,b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1;i<=n;i++){
		if(c[i]==-1)dfs(i,0);//确保节点都访问。
	}
	if(!f)cout<<"-1\n";
	else{
        cout<<ans.size()<<'\n';
		for(int j:ans){
			cout<<j<<' ';
		}cout<<'\n';
	}
}
int main(){
	int T=1;
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>T;
	while(T--)solve();
}

代码中可能有的问题

DFS 时遇到了符合要求且曾经访问过但不在 pa 中的点怎么办？& 为什么能用以上方法求出一个奇环？

不会遇到，曾经访问过的未找到符合要求边的节点，在后续的 DFS 中没有影响。如图，若代码先将1、2、3、4、5、6进入缓存栈中，5、6在后续出栈，5、6虽然被访问但是是对后续没有任何作用才出栈的。所以用该方法是可行的。

温馨提示

由于没规定所有点都连通，所以可能有多个分离的点集合，所以不能特判 $n \le m-1$ 输出 -1。况且要保证每个点都访问。