欧拉图
- 欧拉通路
- 欧拉回路
定义
欧拉通路 (欧拉迹): 通过图中每条边且只通过一次，并且经过每一顶点的通路。
**欧拉回路 (欧拉闭迹): ** 通过图中每条边且只通过一次，并且经过每一顶点的回路。
**欧拉图: ** 存在欧拉回路的图。
无向图是否具有欧拉通路或回路的判定
欧拉通路
只有 2 个度为奇数的节点 (就是欧拉通路的 2 个端点)。
欧拉回路
所有节点度均为偶数。
有向图是否具有欧拉通路或回路的判定
欧拉通路
除 2 个端点外其余节点入度 = 出度；
终点入度比出度大 1，起点入度比出度小 1。
欧拉回路
所有节点入度 = 出度
有向图寻找找欧拉路径 & 回路
/*
work by:Ariel_
Sorce:
Knowledge:欧拉路径
Time:
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <stack>
#define ll long long
#define rg register
using namespace std;
const int MAXN = 1e6 + 5;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int n, m, ind[MAXN], out[MAXN], cnt1, cnt2, st = 1, start[MAXN], fag;
vector<int>e[MAXN];
stack<int> s;
void dfs(int x) {
for (int i = start[x]; i < e[x].size(); i = start[x]) {
int v = e[x][i];
start[x] = i + 1;
dfs(v);
}
s.push(x);
}
int main(){
n = read(), m = read();
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
ind[v]++, out[u]++;
e[u].push_back(v);
}
for (int i = 1; i <= n; i++) {
if(ind[i] != out[i]) { fag = 1;
if(ind[i] + 1 == out[i]) st = i, cnt1++;
else if(ind[i] == out[i] + 1) cnt2++;
}
}
if(!(!fag || (cnt1 == cnt2 && cnt1 == 1))) {printf("No
"); return 0;}
for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
dfs(st);
while(!s.empty()) {
printf("%d ", s.top());
s.pop();
}
return 0;
}
无向图寻找欧拉路径&回路
P2731 [USACO3.3]骑马修栅栏 Riding the Fences
/*
work by:Ariel_
Sorce:
Knowle:无向图欧拉路径, 回路
Time:O(nlogn)
*/
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <vector>
#include <map>
#define ll long long
#define rg register
using namespace std;
const int MAXN = 1100;
int read(){
int x = 0,f = 1; char c = getchar();
while(c < '0'||c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {x = x*10 + c - '0'; c = getchar();}
return x*f;
}
int m, n, ind[MAXN], st, start[MAXN];
vector<int>e[MAXN];
map<pair<int, int>, int> mp;
stack<int> ans;
void dfs(int x) {
while(1) {
while(start[x] < e[x].size() && !mp[make_pair(x, e[x][start[x]])]) start[x]++;
if(start[x] >= e[x].size()) break;
int v = e[x][start[x]];
mp[make_pair(x, v)]--;
mp[make_pair(v, x)]--;
start[x]++;
dfs(v);
}
ans.push(x);
}
int main(){
m = read(), st = n = 500;
for (int i = 1; i <= m; i++) {
int u = read(), v = read();
ind[u]++, ind[v]++;
st = min(st, min(u, v));
e[u].push_back(v), e[v].push_back(u);
mp[make_pair(u, v)]++, mp[make_pair(v, u)]++;
}
for (int i = 1; i <= n; i++) sort(e[i].begin(), e[i].end());
for (int i = 1; i <= n; i++) if(ind[i] & 1) {st = i; break;}
dfs(st);
while(!ans.empty()) {
printf("%d
", ans.top());
ans.pop();
}
puts("");
return 0;
}