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
|
// Laufzeit: O(|V|+|E|)
vector< vector<int> > adjlist, otherIdx;
vector<int> cycle, validIdx;
// Vertauscht Kanten mit Indizes a und b von Knoten n.
void swapEdges(int n, int a, int b) {
int neighA = adjlist[n][a], neighB = adjlist[n][b];
int idxNeighA = otherIdx[n][a], idxNeighB = otherIdx[n][b];
swap(adjlist[n][a], adjlist[n][b]);
swap(otherIdx[n][a], otherIdx[n][b]);
otherIdx[neighA][idxNeighA] = b;
otherIdx[neighB][idxNeighB] = a;
}
// Entfernt Kante i von Knoten n (und die zugehörige Rückwärtskante).
void removeEdge(int n, int i) {
int other = adjlist[n][i];
if (other == n) { //Schlingen.
validIdx[n]++;
return;
}
int otherIndex = otherIdx[n][i];
validIdx[n]++;
if (otherIndex != validIdx[other]) {
swapEdges(other, otherIndex, validIdx[other]);
}
validIdx[other]++;
}
// Findet Eulerzyklus an Knoten n startend.
// Teste vorher, dass Graph zusammenhängend ist! Isolierten Knoten?
// Teste vorher, ob Eulerzyklus überhaupt existiert!
void euler(int n) {
while (validIdx[n] < (int)adjlist[n].size()) {
int nn = adjlist[n][validIdx[n]];
removeEdge(n, validIdx[n]);
euler(nn);
}
cycle.push_back(n); // Zyklus in cycle in umgekehrter Reihenfolge.
}
|
