欧拉路径 & P7771 【模板】欧拉路径

传送门

解题思路

直接用洛谷题解！

说的好！

怎么求有向图的欧拉路径呢？

如果有起点，从起点出发，然后不断dfs，对每个点记录其出边已经到了哪一条，然后当一个点的出边都遍历完的时候就把这条边加入栈中。

这样就找到了一条合法的欧拉路径。

可以使用当前弧优化，时间优化到O(n+m)。

这个题因为要求字典序最小，所以可以先对每个节点的出边按照出点编号sort一遍。

所以用vector存图便于sort。

AC代码

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=2e5+5;
vector ve[maxn];
stack s;
int now[maxn],n,m,in[maxn],out[maxn],vis1,vis2;
void dfs(int u){
	for(int i=now[u];i>n>>m;
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		ve[u].push_back(v);
		out[u]++;
		in[v]++;
	}
	for(int i=1;i<=n;i++){
		if(in[i]==out[i]) continue;
		if(in[i]-out[i]==1){
			if(!vis1) vis1=i;
			else{
				cout<<"No";
				return 0;
			}
			continue;
		}
		if(out[i]-in[i]==1){
			if(!vis2) vis2=i;
			else{
				cout<<"No";
				return 0;
			}
			continue;
		}
		cout<<"No"<
题解知识点模板洛谷题解欧拉路径

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

2019CSP-S初赛知识点汇总

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

关于摄像头知识点

HttpURLConnection发送中文乱码问题解决

《小学知识点》隐私政策

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

二分查找模板（准确找定值）

beautiful 模板

P7715 「EZEC-10」Shape 题解

标签