P7771 【模板】欧拉路径
\(P7771\) 【模板】欧拉路径
题目描述
求有向图字典序最小的欧拉路径。
输入格式
第一行两个整数 \(n,m\) 表示有向图的点数和边数。
接下来 \(m\) 行每行两个整数 \(u,v\) 表示存在一条 \(u\to v\) 的有向边。
输出格式
如果不存在欧拉路径，输出一行 No。
否则输出一行 \(m+1\) 个数字，表示字典序最小的欧拉路径。
样例 #1
样例输入 #1
4 6
1 3
2 1
4 2
3 3
1 2
3 4
样例输出 #1
1 2 1 3 3 4 2
样例 #2
样例输入 #2
5 5
1 2
3 5
4 3
3 4
2 3
样例输出 #2
1 2 3 4 3 5
样例 #3
样例输入 #3
4 3
1 2
1 3
1 4
样例输出 #3
No
提示
对于 \(50\%\) 的数据，\(n,m\leq 10^3\)。
对于 \(100\%\) 的数据，\(1\leq u,v\leq n\leq 10^5\)，\(m\leq 2\times 10^5\)。
保证将有向边视为无向边后图连通。
链式前向星解法
#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = N << 2;
typedef pair<int, int> PII;
int n, m; // n个节点，m条边
PII g[M]; // 用于排序边的临时数组
int start; // 起点
int din[N], dout[N]; // 入度与出度
int ans[M], al; // 记录欧拉路径
int tj[3]; // tj[0]:出度与入度不一致的数量；tj[1]:起点数量; tj[2]:终点数量
// 链式前向星
int e[M], h[N], idx, w[M], ne[M];
void add(int a, int b, int c = 0) {
e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
int st[M]; // 某条边是否已访问过
void dfs(int u) {
for (int i = h[u]; ~i; i = h[u]) { // 删边，链表头指向了下一条边
if (st[i]) { // i这条边已被访问过
h[u] = ne[i]; // 删边，链表头指向了下一条边
continue;
}
// 如果i这条边没有被访问过
st[i] = 1; // 标识已访问
h[u] = ne[i]; // 跳到下一条边
dfs(e[i]); // 处理子节点
}
ans[++al] = u; // 这个点是在循环外加入路径的，注意，与边的那份代码可不一样啊！
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P7771.in", "r", stdin);
#endif
// 初始化链式前向星
memset(h, -1, sizeof h);
// n个顶点，m条边
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) scanf("%d %d", &g[i].first, &g[i].second); // 用一个PII(点对)的数组先把边保存下来，排序完后，再存入链式前向星中
sort(g, g + m, greater<PII>()); // 一维由大到小排序，如果一维一样，那么二维也是由大到小排序。如此，则最后一个遍历到的就是字典序最小的
for (int i = 0; i < m; i++) {
add(g[i].first, g[i].second); // 排序完再用链式前向星建图
dout[g[i].first]++, din[g[i].second]++; // 有向图，维护入度和出度
}
int start = 1;
for (int i = 1; i <= n; i++) {
if (dout[i] != din[i]) tj[0]++; // 出度入度不一致的数量
if (dout[i] - din[i] == 1) tj[1]++, start = i; // 出度比入度大1的数量，一般理解为起点
if (din[i] - dout[i] == 1) tj[2]++; // 入度比出度大1的数量，一般理解为终点
}
// 有向图是否存在欧拉路径
// ① 如果所有点的出度入度全一致，则存在欧拉路径
// ② 如果所有的点出度入度不全一致，那么必须 出度-入度=1 和 入度-出度=1 的节点各有1个
if (tj[0] && (tj[1] != 1 || tj[2] != 1)) {
puts("No");
return 0;
}
// 如果上面出现了环形的情况，那么start=0,此时，需要找出号最小的出发点，本题比较让人省心，直接写1就行了
// 可是有的题不行，它规定最小的号不是1，而是10，所以，你只能再用循环，由小到大去找出号最小，而且有出边的节点
// if (start == 0) {
// for (start = 1; start <= n; start++)
// if (~h[start]) break;
// }
dfs(start);
// 查找欧拉路径
// dfs(start);
// 输出欧拉路径
for (int i = al; i; i--) printf("%d ", ans[i]);
return 0;
}
邻接表解法
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
// 求有向图字典序最小的欧拉路径
int n, m; // n个顶点，m条边
int din[N], dout[N]; // 入度、出度
vector<int> g[N]; // 邻接表
int ans[M], al; // 结果数组
int tj[3]; // tj[0]:出度与入度不一致的数量；tj[1]:起点数量; tj[2]:终点数量
// h[u]是u的出边已经删了多少条，即走过多少条
int h[N];
void dfs(int u) {
// 按指向点的字典序遍历出边，略过已经删掉的边
for (int i = h[u]; i < g[u].size(); i = h[u]) {
h[u]++;
dfs(g[u][i]);
}
ans[++al] = u;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("P7771.in", "r", stdin);
#endif
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int a, b;
scanf("%d%d", &a, &b); // 有向图
g[a].push_back(b); // 记录a->b 有一条边
dout[a]++, din[b]++; // a出度+1， b入度+1
}
int start = 1;
for (int i = 1; i <= n; i++) {
if (dout[i] != din[i]) tj[0]++; // 出度入度不一致的数量
if (dout[i] - din[i] == 1) tj[1]++, start = i; // 起点数
if (din[i] - dout[i] == 1) tj[2]++; // 终点数
}
// 有向图是否存在欧拉路径
// ① 如果所有点的出度入度全一致，则存在欧拉路径
// ② 如果所有的点出度入度不全一致，那么必须 出度-入度=1 和 入度-出度=1 的节点各有1个
if (tj[0] && (tj[1] != 1 || tj[2] != 1)) {
puts("No");
return 0;
}
// 为了完成字典序输出，需要对每个节点出发的边按对边点号由小到大进行排序
for (int i = 1; i <= n; i++) sort(g[i].begin(), g[i].end());
// 开始搜索欧拉路径
dfs(start);
// 输出欧拉路径
for (int i = al; i; i--) printf("%d ", ans[i]);
return 0;
}