P7771

【模板】欧拉路径

题目描述

求有向图字典序最小的欧拉路径。

输入格式

第一行两个整数 $n,m$ 表示有向图的点数和边数。

接下来 $m$ 行每行两个整数 $u,v$ 表示存在一条 $u\to v$ 的有向边。

输出格式

如果不存在欧拉路径，输出一行 No。

否则输出一行 $m+1$ 个数字，表示字典序最小的欧拉路径。

输入输出样例

输入样例 #1

输出样例 #1

1 2 1 3 3 4 2

输入样例 #2

输出样例 #2

1 2 3 4 3 5

输入样例 #3

输出样例 #3

No

说明/提示

对于 $50\%$ 的数据， $n,m\leq 10^3$ 。

对于 $100\%$ 的数据， $1\leq u,v\leq n\leq 10^5$ ， $m\leq 2\times 10^5$ 。

保证将有向边视为无向边后图连通。

本题的数据生成器：

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;
typedef unsigned long long ull;
#define N 100005
#define For(i,x,y)for(i=x;i<=(y);i++)
bool bo[N];
queue<int>p,q;
ull R=GetTickCount();
int deg[N][2],dep[N],fa[N];
inline int Rand(int _,int __)
{
	R^=R<<13;
	R^=R>>7;
	R^=R<<17;
	return R%(__-_+1)+_;
}
int find(int p)
{
	if(p!=fa[p])fa[p]=find(fa[p]);
	return fa[p];
}
inline void unite(int p,int q)
{
	p=find(p),q=find(q);
	if(p==q)return;
	if(dep[p]<dep[q])fa[p]=q;
	else fa[q]=p;
	if(dep[p]==dep[q])dep[p]++;
}
int main()
{
	freopen("P7771.in","w",stdout);
	int n=Rand(1,100000),m=Rand(190000,200000),i,u,v;
	cout<<n<<' '<<m;
	For(i,1,n)fa[i]=i;
	For(i,1,m>>1)
	{
		u=Rand(1,n),v=Rand(1,n);
		cout<<endl<<u<<' '<<v;
		unite(u,v);
		deg[u][0]++;
		deg[v][1]++;
	}
	m-=m>>1;
	For(i,1,n)
	if(deg[i][0]<deg[i][1])p.push(i);
	else if(deg[i][0]>deg[i][1])q.push(i);
	while(m)
	{
		if(p.empty()||q.empty())break;
		u=p.front();
		v=q.front();
		p.pop();
		q.pop();
		unite(u,v);
		cout<<endl<<u<<' '<<v;
		deg[u][0]++;
		deg[v][1]++;
		if(deg[u][0]<deg[u][1])p.push(u);
		if(deg[v][0]>deg[v][1])q.push(v);
		m--;
	}
	For(i,1,n-1)
	if(find(i)!=find(n))
	{
		cout<<endl<<n<<' '<<i<<endl<<i<<' '<<n;
		m-=2;
		unite(n,i);
	}
	if(m<2)
	while(1);
	while(m>Rand(0,1))
	{
		u=Rand(1,n);
		cout<<endl<<u<<' '<<u;
		m--;
	}
	if(m)cout<<endl<<Rand(1,n)<<' '<<Rand(1,n);
	return 0;
}

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P7771 【模板】欧拉路径题解 Author: Yuyi 题目分析与推导过程这道题是一道非常经典的图论模板题：求有向图的欧拉路径，并且要求字典序最小。欧拉路径是指在一个图中，恰好经过每一条边一次的路径。判定欧拉路径存在性的核心条件：对于有向图，要存在欧拉路径，所有的点必须严格满足以下两种情况之一： 1. 欧拉回路（起点和终点重合）：图中所有顶…

点击展开完整题解点击收起题解

2026年8月10日 18:48

P7771 【模板】欧拉路径题解

Author: Yuyi

题目分析与推导过程

这道题是一道非常经典的图论模板题：求有向图的欧拉路径，并且要求字典序最小。 欧拉路径是指在一个图中，恰好经过每一条边一次的路径。

判定欧拉路径存在性的核心条件： 对于有向图，要存在欧拉路径，所有的点必须严格满足以下两种情况之一：

欧拉回路（起点和终点重合）：图中所有顶点的入度都等于出度（in[u] == out[u]）。
欧拉通路（起点和终点不同）：图中有且仅有一个顶点满足 out[u] - in[u] == 1（作为起点 $S$ ），有且仅有一个顶点满足 in[u] - out[u] == 1（作为终点 $T$ ），其余所有顶点的入度必须严格等于出度。

如果全图的入度和出度不满足上述任何一种情况，则一定不存在欧拉路径，直接输出 No。

如何求出字典序最小的路径：

排序： 因为题目要求字典序最小，所以我们在找下一个访问点时，应该优先走向编号较小的点。因此，我们在存图之后，将每个点相连的出边目标节点进行一次升序排序。
Hierholzer 算法（DFS 删边法）：
- 确定好起点 $S$ 后（如果是欧拉回路，我们就找全局第一个有出边的点作为起点），开始进行 DFS 遍历。
- 为了保证每条边只被走一次且不超时，我们使用一个 cur 数组（这叫当前弧优化）来记录当前节点 u 的边已经遍历到了第几条。这能避免每次回溯时重新扫描走过的边，将时间复杂度从 $O(M^2)$ 降到真正的 $O(M)$ 。
- 在 DFS 深入到“死胡同”无路可走时（即当前节点的所有出边都已经走完），我们把当前节点加入到最终答案序列中。
倒序输出： DFS 的过程本质是在“拆解”环和路径，最先由于无路可走而进入答案序列的点，其实是欧拉路径的真正终点。所以最终我们需要将答案序列逆序输出，这样就是一条字典序最小的完美欧拉路径。

正解代码

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 1e5+5;
const int maxm = 2e5+5;
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m;
int in[maxn],out[maxn];
vector<int> G[maxn];
int cur[maxn];
int ans[maxm],cnt;

void dfs(int u)
{
    // 利用 cur 数组进行当前弧优化，避免重复遍历已走的边
    while(cur[u] < G[u].size())
    {
        int v = G[u][cur[u]++];
        dfs(v);
    }
    // 当该点再也走不出去时，将其压入答案栈中
    ans[++cnt] = u;
}

void solve()
{
    read(n),read(m);
    rep(i,1,m)
    {
        int u,v;
        read(u),read(v);
        G[u].push_back(v);
        out[u]++;
        in[v]++;
    }
    
    // 贪心，为了字典序最小，对每个邻接表进行升序排序
    rep(i,1,n)
    {
        if(out[i] > 0) sort(G[i].begin(),G[i].end());
    }
    
    int S = 0,T = 0,fail = 0,start_node = 1;
    bool has_edge = false;
    
    rep(i,1,n)
    {
        if(out[i] > 0)
        {
            if(!has_edge)
            {
                start_node = i;
                has_edge = true;
            }
        }
        if(in[i] != out[i])
        {
            if(out[i] - in[i] == 1) // 唯一可能的起点
            {
                if(S == 0) S = i;
                else fail = 1; // 起点不止一个，宣告失败
            }
            else if(in[i] - out[i] == 1) // 唯一可能的终点
            {
                if(T == 0) T = i;
                else fail = 1; // 终点不止一个，宣告失败
            }
            else fail = 1; // 存在其它奇葩度数，宣告失败
        }
    }
    
    // 如果存在非法度数，或者起点终点不成对出现
    if(fail || (S != 0 && T == 0) || (S == 0 && T != 0))
    {
        cout << "No\n";
        return;
    }
    
    // 若是欧拉回路（无明显的起点终点），选取第一个有出边的点作为起点起步
    if(S == 0) S = start_node; 
    
    dfs(S);
    
    // 如果走到最后发现边没有被全走完，说明图存在独立的不连通边，也不存在欧拉路径
    if(cnt != m + 1)
    {
        cout << "No\n";
        return;
    }
    
    // 答案压在栈里，必须逆序输出
    dep(i,cnt,1)
    {
        cout << ans[i] << (i == 1 ? "" : " ");
    }
    cout << "\n";
    return;
}

int main()
{
    int T_case=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T_case);
    while(T_case--) solve();
    return 0;
}

Generated by Gemini 3.1 Pro

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。