欧拉图、哈密顿图

欧拉图

OI-Wiki 原文

定义

通过图中所有边恰好一次且行遍所有顶点的 通路 称为欧拉通路。

通过图中所有边恰好一次且行遍所有顶点的 回路 称为欧拉回路。

具有欧拉回路 的无向图或有向图称为 欧拉图 。

具有欧拉通路但不具有欧拉回路 的无向图或有向图称为 半欧拉图 。

非形式化地讲，欧拉图就是从 任意一个点 开始都可以一笔画完整个图，半欧拉图必须从 某个点 开始才能一笔画完整个图 。

求欧拉回路 (/) 欧拉通路

常用的是 (operatorname{Hierholzer}) 算法，也称逐步插入回路法 。

从一条回路开始，每次任取一条目前回路中的点，将其替换为一条简单回路，以此寻找到一条欧拉回路。如果从路开始的话，就可以寻找到一条欧拉路。

优化：将找回路的 (operatorname{DFS}) 和 (operatorname{Hierholzer}) 算法的递归合并，边找回路边使用 (operatorname{Hierholzer}) 算法。

时间复杂度：(O(n+mlog m))

核心代码：(例题如：P1341 无序字母对 、P2731 [USACO3.3]骑马修栅栏 )

复制代码#define Maxn 100005 #define Maxm 200005 int n,m,tot,cnt,rt=inf,tp; int hea[Maxn],nex[Maxm],ver[Maxm]; int deg[Maxn],sta[Maxm]; struct Data { int From,To; }Edge[Maxm]; void dfs(int x,int D) { if(hea[x]>0) for(int i=hea[x];i && hea[x];i=nex[i]) hea[x]=nex[i],dfs(ver[i],D+1); // hea 要在循环内判断 sta[++tp]=x; // 及时舍去已经走过的路径！！！ } bool cmp(Data x,Data y) { if(x.From!=y.From) return x.From<y.From; return x.To>y.To; } n=rd(),m=rd(); for(int i=1,x,y;i<=m;i++) x=rd(),y=rd(),Edge[i]=(Data){x,y},deg[x]++,deg[y]--,rt=min(rt,min(x,y)); sort(Edge+1,Edge+m+1,cmp); for(int i=1;i<=m;i++) add(Edge[i].From,Edge[i].To); for(int i=1;i<=n;i++) { if(deg[i]) cnt++,rt=(deg[i]>0)?i:rt; if(deg[i]<-1 || deg[i]>1) cnt=inf; } if(cnt!=0 && cnt!=2) printf("Non"); else { dfs(rt,0); for(int i=tp;i>=1;i--) printf("%d ",sta[i]); printf("n"); }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#define Maxn 100005
#define Maxm 200005
int n,m,tot,cnt,rt=inf,tp;
int hea[Maxn],nex[Maxm],ver[Maxm];
int deg[Maxn],sta[Maxm];
struct Data { int From,To; }Edge[Maxm];
void dfs(int x,int D)
{
if(hea[x]>0) for(int i=hea[x];i && hea[x];i=nex[i])
hea[x]=nex[i],dfs(ver[i],D+1); // hea 要在循环内判断
sta[++tp]=x; // 及时舍去已经走过的路径！！！
}
bool cmp(Data x,Data y)
{
if(x.From!=y.From) return x.From<y.From;
return x.To>y.To;
}
n=rd(),m=rd();
for(int i=1,x,y;i<=m;i++) x=rd(),y=rd(),Edge[i]=(Data){x,y},deg[x]++,deg[y]--,rt=min(rt,min(x,y));
sort(Edge+1,Edge+m+1,cmp);
for(int i=1;i<=m;i++) add(Edge[i].From,Edge[i].To);
for(int i=1;i<=n;i++)
{
if(deg[i]) cnt++,rt=(deg[i]>0)?i:rt;
if(deg[i]<-1 || deg[i]>1) cnt=inf;
}
if(cnt!=0 && cnt!=2) printf("Non");
else
{
dfs(rt,0);
for(int i=tp;i>=1;i--) printf("%d ",sta[i]);
printf("n");
}

---

哈密顿图

OI-Wiki 原文