forked from spaghetti-source/algorithm
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patheulerian_path_undirected.cc
More file actions
104 lines (95 loc) · 2.34 KB
/
eulerian_path_undirected.cc
File metadata and controls
104 lines (95 loc) · 2.34 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//
// Undirected Eulerian Path (Hierholzer's algorithm)
//
// Description:
// A path (walk) P is Eulerian if P visits all edges exactly once.
// A graph admits Eulerian path if and only if there are exactly two
// odd-degree vertices (they are initial and terminal of a path).
//
// Algorithm:
// Hierholzer's algorithm performs DFS from the initial vertex.
//
// Complexity:
// O(n + m)
//
// Verified:
// UVA 10054 The Necklace (tour)
//
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
#define fst first
#define snd second
#define all(c) ((c).begin()), ((c).end())
struct graph {
int n;
struct edge { int src, dst, rev; };
vector<vector<edge>> adj;
graph() : n(0) { }
//graph(int n) : n(n), adj(n) { }
void add_edge(int src, int dst) {
n = max(n, max(src, dst)+1);
if (adj.size() < n) adj.resize(n);
adj[src].push_back({src, dst, (int)adj[dst].size()});
adj[dst].push_back({dst, src, (int)adj[src].size()-1});
}
// destructive
vector<int> path;
void visit(int u) {
while (!adj[u].empty()) {
auto e = adj[u].back();
adj[u].pop_back();
if (e.src >= 0) {
adj[e.dst][e.rev].src = -1;
visit(e.dst);
}
}
path.push_back(u);
}
vector<int> eulerian_path() {
int m = 0, s = -1;
for (int u = 0; u < n; ++u) {
m += adj[u].size();
if (adj[u].size() % 2 == 1) s = u;
}
path.clear(); if (s >= 0) visit(s);
if (path.size() != m/2 + 1) return {};
return path;
}
vector<int> eulerian_tour() {
int m = 0, s = 0;
for (int u = 0; u < n; ++u) {
m += adj[u].size();
if (adj[u].size() > 0) s = u;
}
path.clear(); visit(s);
if (path.size() != m/2 + 1 || path[0] != path.back()) return {};
return path;
}
};
int main() {
int ncase;
scanf("%d", &ncase);
for (int icase = 0; icase < ncase; ++icase) {
if (icase > 0) printf("\n");
printf("Case #%d\n", icase+1);
int m;
scanf("%d", &m);
graph g;
for (int i = 0; i < m; ++i) {
int s, t;
scanf("%d %d", &s, &t);
g.add_edge(s-1, t-1);
}
auto path = g.eulerian_tour();
if (path.empty()) {
printf("some beads may be lost\n");
} else {
for (int i = 0; i+1 < path.size(); ++i)
printf("%d %d\n", path[i]+1, path[i+1]+1);
}
}
}