欧拉回路，指遍历图时通过图中每条边且仅通过一次，最终回到起点的一条闭合回路，适用于有向图与无向图，如果不强制要求回到起点，则被称为欧拉路径。
欧拉图：具备欧拉回路的图
- 无向图：图的所有顶点度数都是偶数
- 有向图：图的所有顶点入度与出度相等
1->2->3->4->5->1即为一条欧拉回路，欧拉图可以有多个欧拉回路，其起点不唯一
半欧拉图：具有欧拉路径但不具有欧拉回路
- 无向图：有且仅有两个顶点度数为奇数，这两个点就是欧拉路径的起始点
- 有向图：有且仅有一个顶点出度-入度=1，且有且仅有一个入度-出度=1，这两个即为起始点
1->2->3->1->5->4->3即为一条欧拉路径，1,3为起始点
求取一个图的欧拉路径，可以利用dfs，每遍历一条边就将这条边消去，当遍历到的顶点度数为0时则将其入栈，最后一个个出栈，就是欧拉路径经过的顶点顺序
判断图是否具有欧拉路径
bool iseuler() {
int c=0;
for (int i=1; i<=n; i++) {
if (edge[i]%2==1) c++;
}
if (c>2) return false;//超过两个度数为奇数的点，则不能形成欧拉路径
if (c>0) flag=false;//记录是否为欧拉图，0个奇数度数点则为欧拉图
return true;
}求取欧拉路径
void dfs(int node){
for (int i=1;i<=n;i++){//不断遍历，直到这个顶点度数为0
if (g[node][i]){
g[node][i]=g[i][node]=0;//无向图需要消除双向边，有向图则只消除一条
edge[i]--;
edge[node]--;
dfs(i);//继续遍历下一个顶点
}
}
s.push(node);//度数为0入栈
}
void euler() {
if(flag) {//欧拉图，起点随意
for (int i=1; i<=n; i++)
if (edge[i]) {
dfs(i);
break;
}
}
else {//半欧拉图，起点需要是奇数度点
for (int i=1;i<=n;i++){
if (edge[i]%2==1){
dfs(i);
break;
}
}
}
}完整代码
#include <bits/stdc++.h>
#define maxn 1005
using namespace std;
int n;
int g[maxn][maxn]= {0};
int edge[maxn]={0};
bool flag=true;
stack<int> s;
bool iseuler() {
int c=0;
for (int i=1; i<=n; i++) {
if (edge[i]%2==1) c++;
}
if (c>2) return false;
if (c>0) flag=false;
return true;
}
void dfs(int node){
for (int i=1;i<=n;i++){
if (g[node][i]){
g[node][i]=g[i][node]=0;
edge[i]--;
edge[node]--;
dfs(i);
}
}
s.push(node);
}
void euler() {
if(flag) {
for (int i=1; i<=n; i++)
if (edge[i]) {
dfs(i);
break;
}
}
else {
for (int i=1;i<=n;i++){
if (edge[i]%2==1){
dfs(i);
break;
}
}
}
}
int main() {
cin>>n;
int x,y;
int k=n;
while(k--) {
cin>>x>>y;
g[x][y]=g[y][x]=1;
edge[x]++;
edge[y]++;
}
if (!iseuler()) {
cout<<"false";
return 0;
}
euler();
while(!s.empty()){
cout<<s.top()<<' ';
s.pop();
}
return 0;
}运行结果
相关题目
. - 力扣（LeetCode）
力扣753 破解保险箱
示例 1：
输入：n = 1, k = 2 输出："10" 解释：密码只有 1 位，所以输入每一位就可以。"01" 也能够确保打开保险箱。
示例 2：
输入：n = 2, k = 2 输出："01100" 解释：对于每种可能的密码： - "00" 从第 4 位开始输入。 - "01" 从第 1 位开始输入。 - "10" 从第 3 位开始输入。 - "11" 从第 2 位开始输入。 因此 "01100" 可以确保打开保险箱。"01100"、"10011" 和 "11001" 也可以确保打开保险箱。
以n=3举例，我们可以将所有n-1长度的密码组合00,01,10,11看作四个顶点，它们的边即为可能的保险箱密码，求取此图欧拉回路即可
//欧拉回路
#define mod
bool book[10000];
char ans[10000];
int kk,l,m;
void dfs(int node){
for (int i=0;i<kk;i++){
int edge=node*10+i;
if(!book[edge]){
book[edge]=true;
dfs(edge%m);
ans[l++]=i+'0';
}
}
}
char* crackSafe(int n, int k) {
m=pow(10,n-1);
memset(book,false,sizeof(book));
memset(ans,0,sizeof(ans));
kk=k;
l=0;
book[0]=true;
dfs(0);
for (int i=0;i<n;i++){
ans[l++]='0';
}
return ans;
}
