欧拉图
- 欧拉路径:恰好经过每条边一次;
- 欧拉回路:起点和终点相同的欧拉路径;
- 欧拉图:存在一条欧拉路径的图;
欧拉图的判定
- 对于有向图 \(G=(V,E)\),当且仅当 \(\forall u\in V,\ deg_{in}(u)=deg_{out}(u)\),图存在欧拉回路;
- 对于无向图 \(G=(V,E)\),当且仅当 \(\forall u\in V,\ 2\mid deg(u)\),图存在欧拉回路;
对于欧拉路径,我们可以将其视为一个欧拉回路去掉一条边。因此,有向图存在欧拉路径的条件是仅两个点入度和出度相差 \(1\),无向图存在欧拉路径的条件是仅两个点度数为奇数。这两个点就分别是起点和终点。
寻找欧拉路径和欧拉回路
- 访问到点 \(u\);
- 遍历其所有没有访问过的出边 \((u,v)\);
- 标记 \((u,v)\) 为访问过;
- 递归访问 \(v\);
- 将当前点入栈;
将栈中元素依次弹出,即得一条欧拉路径(回路)
因为题目中要求输出字典序最小的欧拉回路,因此选择编号最小的点作为起点,通过排序使其总是先访问编号较小的点。
代码
| #include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N = 1E5 + 10;
int n, m;
vector<int> adj[N];
int cur[N];
int ind[N], otd[N];
int sta[N], top;
void dfs(int u) {
for(int i = cur[u]; i < (int)adj[u].size(); i = max(i + 1, cur[u])) {
cur[u]++;
dfs(adj[u][i]);
}
sta[++top] = u;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
ind[v]++;
otd[u]++;
}
for(int i = 1; i <= n; i++) {
sort(adj[i].begin(), adj[i].end());
}
bool flag = true;
int beg = 0, end = 0;
for(int i = 1; i <= n; i++) {
if(ind[i] != otd[i]) flag = false;
if(ind[i] == otd[i] + 1) {
if(end != 0) end = -1;
else end = i;
} else if(ind[i] + 1 == otd[i]) {
if(beg != 0) beg = -1;
else beg = i;
} else if(ind[i] != otd[i]) {
beg = end = -1;
}
}
if(!flag && !(beg > 0 && end > 0)) {
cout << "No" << endl;
return 0;
}
if(flag) beg = 1;
dfs(beg);
while(top > 0) {
cout << sta[top--] << ' ';
}
cout << endl;
return 0;
}
|