网站建设亿玛酷技术,常州网上教科院,台州网站设计公司,中国100强排名企业名单欧拉回路#xff0c;指遍历图时通过图中每条边且仅通过一次#xff0c;最终回到起点的一条闭合回路#xff0c;适用于有向图与无向图#xff0c;如果不强制要求回到起点#xff0c;则被称为欧拉路径。
欧拉图#xff1a;具备欧拉回路的图
无向图#xff1a;图的所有顶…欧拉回路指遍历图时通过图中每条边且仅通过一次最终回到起点的一条闭合回路适用于有向图与无向图如果不强制要求回到起点则被称为欧拉路径。
欧拉图具备欧拉回路的图
无向图图的所有顶点度数都是偶数有向图图的所有顶点入度与出度相等 1-2-3-4-5-1即为一条欧拉回路欧拉图可以有多个欧拉回路其起点不唯一
半欧拉图具有欧拉路径但不具有欧拉回路
无向图有且仅有两个顶点度数为奇数这两个点就是欧拉路径的起始点有向图有且仅有一个顶点出度-入度1且有且仅有一个入度-出度1这两个即为起始点 1-2-3-1-5-4-3即为一条欧拉路径1,3为起始点
求取一个图的欧拉路径可以利用dfs每遍历一条边就将这条边消去当遍历到的顶点度数为0时则将其入栈最后一个个出栈就是欧拉路径经过的顶点顺序
判断图是否具有欧拉路径
bool iseuler() {int c0;for (int i1; in; i) {if (edge[i]%21) c;}if (c2) return false;//超过两个度数为奇数的点则不能形成欧拉路径if (c0) flagfalse;//记录是否为欧拉图0个奇数度数点则为欧拉图return true;
}
求取欧拉路径
void dfs(int node){for (int i1;in;i){//不断遍历直到这个顶点度数为0if (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 i1; in; i)if (edge[i]) {dfs(i);break;}}else {//半欧拉图起点需要是奇数度点for (int i1;in;i){if (edge[i]%21){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 flagtrue;
stackint s;
bool iseuler() {int c0;for (int i1; in; i) {if (edge[i]%21) c;}if (c2) return false;if (c0) flagfalse;return true;
}void dfs(int node){for (int i1;in;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 i1; in; i)if (edge[i]) {dfs(i);break;}}else {for (int i1;in;i){if (edge[i]%21){dfs(i);break;}}}
}int main() {cinn;int x,y;int kn;while(k--) {cinxy;g[x][y]g[y][x]1;edge[x];edge[y];}if (!iseuler()) {coutfalse;return 0;}euler();while(!s.empty()){couts.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 也可以确保打开保险箱。
以n3举例我们可以将所有n-1长度的密码组合00,01,10,11看作四个顶点它们的边即为可能的保险箱密码求取此图欧拉回路即可
//欧拉回路
#define mod
bool book[10000];
char ans[10000];
int kk,l,m;void dfs(int node){for (int i0;ikk;i){int edgenode*10i;if(!book[edge]){book[edge]true;dfs(edge%m);ans[l]i0;}}
}
char* crackSafe(int n, int k) {mpow(10,n-1);memset(book,false,sizeof(book));memset(ans,0,sizeof(ans));kkk;l0;book[0]true;dfs(0);for (int i0;in;i){ans[l]0;}return ans;
}
