欧拉路径
定义
欧拉路径,指在有向图 G G G 中,可以从起点 v 1 v_1 v1 开始,经过每条边,则此路径为欧拉路径。
欧拉回路,就是在欧拉路径的基础上,限定终点也必须为 v 1 v_1 v1。
判定方法
欧拉回路,其实就是一笔画问题。而根据我们的小学数学可知,如果一个图可以一笔画,则必须满足以下条件之一:
- 有两个节点连边个数为奇数
- 全部节点连边个数为偶数
针对第一条件,则起点就为其中一个奇点,终点为另一个奇点。
第二条件,则起点设在哪里都行,终点也为起点,默认为编号最小的节点。
生成路径
采取 dfs
,每次遍历到一个节点,都将其进栈。最后倒序输出即为欧拉路径。
每遍历到一个节点,都需要判断与其的连边是否已经遍历过,没遍历过则继续遍历指向节点。
朴素代码:
//e[i]:链式前向星
// vis:每条边是否遍历过
void dfs(int u)
{
for(int i=head[u];i;i=e[i].to)//剪枝优化
{
if(vis[i]) continue;
vis[i]=true;
dfs(edge[i].to);
}
st.push(u);
return;
}
例题:P7771 【模板】欧拉路径
朴素版代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int start=1,inn,outn;
bool vis[M];
struct EDGE{
int from,to,pre;
}e[M],edge[M];
int head[N],u,v,cnt_edge;
int in[N],out[N];
void add(int from,int to)
{
edge[++cnt_edge].from=from;
edge[cnt_edge].to=to;
edge[cnt_edge].pre=head[from];
head[from]=cnt_edge;
return;
}
stack<int> st;
void dfs(int u)
{
for(int i=head[u];i;i=e[i].to)
{
if(vis[i]) continue;
vis[i]=true;
dfs(edge[i].to);
}
st.push(u);
return;
}
bool cmp(EDGE a,EDGE b)//简简单单排个序
{
if(a.from!=b.from)
return a.from<b.from;
return a.to>b.to;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].from,&e[i].to);
in[e[i].to]++;out[e[i].from]++;
}
for(int i=1;i<=n;i++)
{
if(abs(in[i]-out[i])>1)//出度与入度差>1,直接排除
{
printf("No\n");
return 0;
}
if(in[i]-out[i]==1)//入度比出度多一,为终点
inn++;//有多少个可以为终点
if(out[i]-in[i]==1)//起点,并标记
{
outn++;//有多少个可以为起点
start=i;
}
}
if((inn==0&&outn==0)||(inn==1&&outn==1))//上文所述的两种判定方法
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
add(e[i].from,e[i].to);
dfs(start);
while(!st.empty())
{
printf("%d ",st.top());
st.pop();
}
}
else
printf("No");
putchar('\n');
return 0;
}
然而,实测只有 90 p t s 90pts 90pts,原因是 dfs
中的遍历没有剪枝,浪费时间。
优化办法:遍历时直接更新 head
数组,免得每次都得遍历 m m m 次。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=2e5+5;
int n,m;
int start=1,inn,outn;
bool vis[M];
struct EDGE{
int from,to,pre;
}e[M],edge[M];
int head[N],u,v,cnt_edge;
int in[N],out[N];
void add(int from,int to)
{
edge[++cnt_edge].from=from;
edge[cnt_edge].to=to;
edge[cnt_edge].pre=head[from];
head[from]=cnt_edge;
return;
}
stack<int> st;
void dfs(int u)
{
for(int i=head[u];i;i=head[u])
{
head[u]=edge[i].pre;
dfs(edge[i].to);
}
st.push(u);
return;
}
bool cmp(EDGE a,EDGE b)
{
if(a.from!=b.from)
return a.from<b.from;
return a.to>b.to;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&e[i].from,&e[i].to);
in[e[i].to]++;out[e[i].from]++;
}
for(int i=1;i<=n;i++)
{
if(abs(in[i]-out[i])>1)
{
printf("No\n");
return 0;
}
if(in[i]-out[i]==1)
inn++;
if(out[i]-in[i]==1)
{
outn++;
start=i;
}
}
if((inn==0&&outn==0)||(inn==1&&outn==1))
{
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
add(e[i].from,e[i].to);
dfs(start);
while(!st.empty())
{
printf("%d ",st.top());
st.pop();
}
}
else
printf("No");
putchar('\n');
return 0;
}