模板 - 欧拉路、欧拉回路（一笔画问题）
发布时间
阅读量：
阅读量
整理的算法模板合集： ACM模板
目录
-
- 非递归版
- 普通递归版
- Hierholzers算法（输出字典序最小的答案）
- Fleury算法
- 究极优化版
- 混合图欧拉回路
欧拉路 就是给一个图，存在一条回路从起点到终点把所边经过且每条边只经过一次 。“一笔画问题 ”
欧拉回路就是从起点遍历所有的边一次最后回到起点
非递归版
解决问题 ：给定一张无向图，求出它的欧拉回路，若不止一条，随意输出一条即可
int head[N],nex[M],ver[M],tot = 1;
bool vis[M];
int stk[M],ans[M];//模拟系统栈、答案栈
int n,m,s,t,cnt,top;
queue<int>q;
void add(int x,int y){
ver[++tot] = y;nex[tot] = head[x];head[x] = tot;
}
void euler(){//模拟dfs递归
stk[++top] = 1;//起点
while(top > 0){
int x = stk[top],i = head[x];
while(i && vis[i])i = nex[i];//找到一条尚未访问过的路
// 与x相连的所有边均已访问，模拟回溯过程，并记录
if(i){
stk[++top] = ver[i];
vis[i] = ver[i ^ 1] = true;//正常的欧拉回路模板
head[x] = nex[i];
}
else {// 与x相连的所有边均已访问，模拟回溯过程，并记录
top--;
ans[++cnt] = x;
}
}
}
int main(){
scanf("%d%d",&n,&m);
tot = 1;
over(i,1,m){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
euler();
over(i,1,cnt)
printf("%d\n",ans[i]);
}
普通递归版
Hierholzers算法（输出字典序最小的答案）
此法输出的是所有合法方案中字典序最小的答案
本算法求出的是倒序的欧拉回路，所以输出的时候要倒序输出才是字典序最小的答案。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
const int N = 5000, M = 50007, INF = 0x3f3f3f3f;
typedef pair<int,int> PII;
int n, m;
int d[N];
int g[N][N];
int ans[M], cnt;
void dfs(int x){
for(int i = 1;i <= 500;++i){
if(g[x][i]){
g[x][i] -- , g[i][x] -- ;
dfs(i);
}
}
ans[ ++ cnt] = x;
}
int main(){
scanf("%d", &n);
for(int i = 1;i <= n;++i){
int x,y;
scanf("%d%d",&x, &y);
g[x][y] ++ , g[y][x] ++ ;
d[y] ++, d[x] ++;
}
int start = 1;
while(!d[start])start ++;
for(int i = 1;i <= 500;++i){
if(d[i] % 2){
start = i;
break;
}
}
dfs(start);
for(int i = cnt;i; -- i)
printf("%d\n",ans[i]);
return 0;
}
输出n+1个字母，使得n个字母对都在这个字符串中出现，因为是n+1个字母，所以我们可以看出来其实就是一个欧拉路径，因为字母对可以替换顺序，所以我们将每个字母对都连一个无向边，建图，求欧拉回路，这样求出来的就是n+1个字母的字符串，因为是欧拉路径，所以会经过每条边，也就是每一个字母对都会在里面出现。
我们要先判断图是否连通（可以直接用并查集判断，或者看欧拉路径是否包含了n+1个点），如果不连通那么我们求出来的欧拉回路也不会包含所有的字母对。然后再判断是否有欧拉路径，判断的方法就是看奇度点的个数是不是0或者2，注意如果是0的话说明有欧拉回路，那么我们以哪一个字母为起点都可以，所以我们取字典序最小的字母作为起点，这样才能求得字典序最小的答案。
注意我们使用Hierholzers算法求出来的是倒序的，所以我们存的时候就可以直接倒着存n+1个字母，然后直接cout输出即可。
int Find(int x){
if(fa[x] == x)return x;
return fa[x] = Find(fa[x]);
}
void dfs(int x){
for(int i = 65; i <= 125 ; ++ i){
if(g[x][i]){
g[x][i] -- , g[i][x] -- ;
dfs(i);
}
}
ans[tot -- ] = x;
}
//找欧拉路径
int main(){
scanf("%d", &n);tot = n;
for(int i = 1; i <= 500; ++ i)
fa[i] = i;
for(int i = 1; i <= n; ++ i){
cin >> s;
int x = s[0], y = s[1];
g[x][y] ++ , g[y][x] ++ ;
d[y] ++ , d[x] ++ ;
int fx = Find(x), fy = Find(y);
fa[fx] = fy;
}
int cnt = 0;
for(int i = 65; i <= 125; ++ i){
if(Find(i) == i && d[i])
cnt ++ ;
}
if(cnt != 1){//多个祖先，说明有孤立点不是连通图。
puts("No Solution");
return 0;
}
cnt = 0;int root = 0;
for(int i = 65; i <= 125; ++ i){
if(d[i] & 1){
if(root == 0)//找字典序最小的起点
root = i;
cnt ++ ;
}
}
if(cnt && cnt != 2){//奇度点为0或者2才存在欧拉路径
puts("No Solution");
return 0;
}
if(root == 0){
//存在欧拉回路，那么任意点都可以作为起点。所以找字典序最小的起点
for(int i = 65; i <= 125; ++ i){
if(d[i]){
root = i;//找到字典序最小的起点
break;
}
}
}
dfs(root);
cout << ans <<endl;
return 0;
}
Fleury算法
void dfs( int u ) {
sta.push(u);
for( register int i = head[u]; i; i = line[i].nxt ) {
if( vis[i] ) continue;
vis[i] = vis[ i ^ 1 ] = true;
dfs( line[i].to );
break;
}
}
void fleury( int st ) {
sta.push(st);
while(!sta.empty() ) {
int flag = 0, u = sta.top(); sta.pop();
for( register int i = head[u]; i; i = line[i].nxt) {
if( vis[i] ) continue;
flag = 1; break;
}
if( !flag ) printf( "%d\n", u );
else dfs(u);
}
}
究极优化版
给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
type为1时图是无向图。
type为0使图是有向图。
如果出题人丧心病狂（200000个1的自环），普通的代码T了可以用这个代码
const int N = 500010, M = 500007, INF = 0x3f3f3f3f;
int n, m;
int type;
int head[N], nex[M], edge[M], ver[M], tot;
int ans[M];
bool used[M];
int cnt;
int din[N], dout[N];
void add(int x,int y){
ver[tot] = y;
nex[tot] = head[x];
head[x] = tot ++ ;
}
void dfs(int x)
{
//特殊数据O(n)优化，固定i引用变量，这样head[x]也会变，达到删边的效果
for(int &i = head[x]; ~i;){
if(used[i]){
i = nex[i];//删边，先删再dfs，防止遍历到祖先节点时该边未被删去
continue;
}
used[i] = true;
if(type == 1)
used[i ^ 1] = true;
int t;
if(type == 1){//无向图就是正反两条边
t = i / 2 + 1;//实际上只有一条，我们建图的时候无向图建了两条
if(i & 1)//奇数就是反向边,根据题意取负数
t = -t;
}
//有向图就是下一条边
else t = i + 1;
int y = ver[i];
i = nex[i];//删边
dfs(y);
ans[++cnt] = t;
}
}
int main(){
scanf("%d",&type);
scanf("%d%d",&n,&m);
memset(head,-1,sizeof head);
for(int i = 1;i <= m;++i){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);
if(type == 1)add(y,x);
din[y] ++ , dout[x] ++ ;
}
//先判断不成立的情况
if(type == 1){
for(int i = 1;i <= n;++i)
if((din[i] + dout[i]) & 1){/*求的是欧拉回路所以奇数度点要为0*/
puts("NO");
return 0;
}
}
else {
for(int i = 1;i <= n;++i){
if(din[i] != dout[i]){
puts("NO");
return 0;
}
}
}
for(int i = 1;i <= n;++i)//找到一个可行的起点，因为本题中的1~n中的点可能没有连边
if(head[i] != -1){
dfs(i);
break;
}
if(cnt < m){//如果不全部连通，则不存在欧拉路
puts("NO");
return 0;
}
puts("YES");
for(int i = cnt;i;i -- )//倒序输出
printf("%d ",ans[i]);
puts("");
return 0;
}
混合图欧拉回路
题目描述:给出一个 V（V<=100）个点和 E（E<=500）
条边的无向边与有向边的混合图，试打印出它的任意一条欧拉回路（无向边的两个方向只能从某个方向经过一次），如果没有输出No euler circuit exist。输入保证图连通。
由于有向图有欧拉回路当且仅当图是弱连通的并且所有点的 入度-出度=0，可以发现关键问题在于如何给无向边定向使得入度-出度=0.
先给所有无向边任意指定一个方向，并令 d’[i]=i的出度-入度（算上原图的有向边和定向了的无向边）。 如果某个 d’[i]
是奇数（相当于说它连接了奇数条边，包括有向边和无向边），那么显然无解，否则令 d[i]=d’[i]/2（为了方便，暂时称其为“度”）。
考虑如果有一条边 u->v 在原图中是无向边，那么将它反向，变成 v->u 之后，u的出度-1，入度+1，从而
d[u]-=1；同理，d[v]+=1. 可以发现这相当于说把 u 的一个度“流到”了 v 的一个度。 于是我们（在网络流中）从 u 到 v
连一条容量为 1 的边，表示可以在 d[u] 中流出一个给 d[v]。 另外，对每个点 u，如果 d[u]>0，那么要从 S 到 u
连一条容量为 d[u] 的边，表示 u 这里多出了 d[u] 的度； 否则 d[u]<=0，就从 u 到 T 连一条容量为 -d[u]
的边，表示 u 这里缺少 -d[u] 的度。 执行一遍最大流之后如果 S
出发的所有弧都满流，就说明所有多出来的度都流出去了（同时所有少的度都补上了，因为少的度的总数 这时候只需要看网络流中哪些 u->v
的边流上了，就知道哪些边需要反向。把这些边反向之后找一遍有向图欧拉回路即可。
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <vector>
typedef long long LL;
int readInt() {
int ans = 0, c, f = 1;
while (!isdigit(c = getchar()))
if (c == '-') f *= -1;
do ans = ans * 10 + c - '0';
while (isdigit(c = getchar()));
return ans * f;
}
const int N = 105;
const int M = 1500;
int n, m, S, T, pre[N], nxt[M], to[M], ret[M], d[N], cnt, sum;
int u[M], v[M], id[M];
std::vector<int> V[N];
inline void addEdge(int x, int y, int r) {
nxt[cnt] = pre[x];
ret[cnt] = r;
to[pre[x] = cnt++] = y;
nxt[cnt] = pre[y];
ret[cnt] = 0;
to[pre[y] = cnt++] = x;
}
bool Init() {
n = readInt(); m = readInt();
S = 0; T = n + 1;
memset(pre, -1, sizeof pre);
cnt = 0;
memset(d, 0, sizeof d);
for (int i = 0; i < m; ++i) {
u[i] = readInt(); v[i] = readInt();
int c;
while (!isalpha(c = getchar()));
++d[u[i]]; --d[v[i]];
if (c == 'U') id[i] = cnt, addEdge(u[i], v[i], 1);
else id[i] = -1;
}
sum = 0;
for (int i = 1; i <= n; ++i) {
if (d[i] & 1) return false;
d[i] /= 2;
if (d[i] > 0) {
addEdge(S, i, d[i]);
sum += d[i];
} else addEdge(i, T, -d[i]);
}
return true;
}
int que[N], dis[N], cur[N];
bool BFS() {
int hd = 0, tl = 0;
memset(dis, -1, sizeof dis);
dis[que[tl++] = S] = 0;
while (hd < tl)
for (int x = que[hd++], i = pre[x]; ~i; i = nxt[i])
if (ret[i] != 0 && dis[to[i]] == -1)
dis[que[tl++] = to[i]] = dis[x] + 1;
return dis[T] != -1;
}
int DFS(int x, int maxf) {
if (x == T) return maxf;
int ans = 0;
for (int &i = cur[x]; ~i; i = nxt[i])
if (ret[i] != 0 && dis[to[i]] == dis[x] + 1) {
int t = DFS(to[i], std::min(ret[i], maxf - ans));
ret[i] -= t;
ret[i ^ 1] += t;
if ((ans += t) == maxf) break;
}
return ans;
}
void Euler(int x) {
while (!V[x].empty()) {
int y = V[x].back(); V[x].pop_back();
Euler(y);
printf(" %d", x);
}
}
void Solve() {
int ans = 0;
while (BFS())
memcpy(cur, pre, sizeof cur), ans += DFS(S, 0x7fffffff);
if (ans != sum) puts("No euler circuit exist");
else {
for (int i = 1; i <= n; ++i) V[i].clear();
for (int i = 0; i < m; ++i)
if (id[i] >= 0 && !ret[id[i]])
V[u[i]].push_back(v[i]);
else
V[v[i]].push_back(u[i]);
printf("1");
Euler(1);
puts("");
}
}
int main() {
int T = readInt();
while (T--) {
if (!Init()) puts("No euler circuit exist");
else Solve();
if (T) puts("");
}
return 0;
}
全部评论 (0)
还没有任何评论哟~