graph/euler.cpp


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

vector< vector<int> > adjlist;
vector< vector<int> > otherIdx;
vector<int> cycle;
vector<int> validIdx;

void swapEdges(int n, int a, int b) { // Vertauscht Kanten mit Indizes a und b von Knoten n.
	int neighA = adjlist[n][a];
	int neighB = adjlist[n][b];
	int idxNeighA = otherIdx[n][a];
	int 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;
}

void removeEdge(int n, int i) { // Entfernt Kante i von Knoten n (und die zugehoerige Rueckwaertskante).
	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 zusammenhaengend ist! (isolierte Punkte sind ok)
//teste vorher, ob Eulerzyklus ueberhaupt 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 am Ende in cycle
}