UVa 302

From Algorithmist
Jump to: navigation, search

302 - John's trip[edit]

Summary[edit]

John's trip is an Eulerian Cycle. This problem is about finding an Eulerian cycle in a connected undirected graph. We can assume that the graphs given are connected in the sense that Johnny can get to any street in the town starting from his house.

Explanation[edit]

Firstly, we need to check if there exists an Eulerian cycle in the given graph. It is an easy task because we know that a connected undirected graph is Eulerian if and only if every vertex has an even degree. After a graph is found to be Eulerian, we can use Fleury's algorithm to construct an Eulerian cycle. We start with John's home vertex. At each step, say, while we are at vertex u, let E[u] be the list of edges that are accidental to u. Since we need to find the Eulerian cycle that is the lexicographically smallest one, we select the edge (u,v) in E[u] that has the smallest ID and satisfies:

  • (u,v) is the only edge that is incidental to u; or
  • u and v are still connected after the deletion of (u,v).

After such an edge (u,v) is found, actually its existence is guaranteed, we add it to the Eulerian cycle and delete it from the graph. The whole process ends when all the edges are in the Eulerian cycle.

Gotchas[edit]

  • John lives in the "smaller" junction of the first street in the input block. By "smaller" I mean the junction has a smaller number than the other one.
  • While outputing the Eulerian cycle, remember to strip of the ending space. Otherwise, you will get a "Presentation Error".

Implementations[edit]

Notes/Hints on actual implementation here.

Input[edit]

1 2 1
2 3 2
3 1 6
1 2 5
2 3 3
3 1 4
0 0
1 2 1
2 3 2
1 3 3
2 4 4
0 0
2 4 3
2 4 4
2 1 1
1 4 2
2 3 5
3 4 6
2 5 7
2 5 8
4 6 9
5 5 15
1 1 16
3 3 14
6 6 17
7 4 13
6 7 10
7 6 11
6 7 12
0 0
2 1 3
2 2 2
2 2 6
2 2 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
2 1 3
2 2 2
2 2 6
2 1 7
2 2 8
1 1 4
1 2 1
1 1 5
0 0
1 2 16
2 1 21
1 4 12
4 1 15
1 3 10
1 3 11
3 1 17
3 1 19
3 2 2
2 3 4
2 7 1
2 7 3
3 7 23
5 7 22
5 3 20
3 4 5
3 4 7
4 6 8
6 4 14
1 1 24
4 4 25
4 4 26
5 6 6
6 5 9
7 6 13
7 6 18
9 1 27
9 9 30
9 8 32
8 8 28
8 8 29
8 8 34
8 10 31
10 4 35
10 10 33
1 8 36
4 8 37
0 0
0 0 

Output[edit]

1 2 3 5 4 6

Round trip does not exist.

1 16 2 3 4 9 10 11 17 12 13 6 14 5 7 15 8

1 2 6 7 8 3 4 5

Round trip does not exist.

10 2 1 3 4 5 7 11 12 8 6 9 13 18 14 15 16 21 17 20 22 23 19 24 27 30 32 28 29 31 33 35 25 26 37 34 36 

References[edit]