欧拉路径/欧拉回路 Hierholzers

欧拉路径/欧拉回路 Hierholzers

欧拉路径：一笔画完图中全部边，画的顺序就是一个可行解；当起点终点相同时称欧拉回路。

有向图欧拉路径存在判定

有向图欧拉路径存在：\(\tt ^1\) 恰有一个点出度比入度多 \(1\) （为起点）；\(\tt ^2\) 恰有一个点入度比出度多 \(1\) （为终点）；\(\tt ^3\) 恰有 \(N-2\) 个点入度均等于出度。如果是欧拉回路，则上方起点与终点的条件不存在，全部点均要满足最后一个条件。

signed main() {int n, m;cin >> n >> m;DSU dsu(n + 1); // 如果保证连通，则不需要 DSUvector<unordered_multiset<int>> ver(n + 1); // 如果对于字典序有要求，则不能使用 unorderedvector<int> degI(n + 1), degO(n + 1);for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;ver[x].insert(y);degI[y]++;degO[x]++;dsu.merge(x, y); // 直接当无向图}int s = 1, t = 1, cnt = 0;for (int i = 1; i <= n; i++) {if (degI[i] == degO[i]) {cnt++;} else if (degI[i] + 1 == degO[i]) {s = i;} else if (degI[i] == degO[i] + 1) {t = i;}}if (dsu.size(1) != n || (cnt != n - 2 && cnt != n)) {cout << "No\n";} else {cout << "Yes\n";}
}

无向图欧拉路径存在判定

无向图欧拉路径存在：\(\tt ^1\) 恰有两个点度数为奇数（为起点与终点）；\(\tt ^2\) 恰有 \(N-2\) 个点度数为偶数。

signed main() {int n, m;cin >> n >> m;DSU dsu(n + 1); // 如果保证连通，则不需要 DSUvector<unordered_multiset<int>> ver(n + 1); // 如果对于字典序有要求，则不能使用 unorderedvector<int> deg(n + 1);for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;ver[x].insert(y);ver[y].insert(x);deg[y]++;deg[x]++;dsu.merge(x, y); // 直接当无向图}int s = -1, t = -1, cnt = 0;for (int i = 1; i <= n; i++) {if (deg[i] % 2 == 0) {cnt++;} else if (s == -1) {s = i;} else {t = i;}}if (dsu.size(1) != n || (cnt != n - 2 && cnt != n)) {cout << "No\n";} else {cout << "Yes\n";}
}

有向图欧拉路径求解（字典序最小）

vector<int> ans;
auto dfs = [&](auto self, int x) -> void {while (ver[x].size()) {int net = *ver[x].begin();ver[x].erase(ver[x].begin());self(self, net);}ans.push_back(x);
};
dfs(dfs, s);
reverse(ans.begin(), ans.end());
for (auto it : ans) {cout << it << " ";
}

无向图欧拉路径求解

auto dfs = [&](auto self, int x) -> void {while (ver[x].size()) {int net = *ver[x].begin();ver[x].erase(ver[x].find(net));ver[net].erase(ver[net].find(x));cout << x << " " << net << endl;self(self, net);}
};
dfs(dfs, s);