UVa 539

From Algorithmist
Jump to navigation Jump to search

539 The Settlers of Catan[edit]

Summary[edit]

Find the longest trail in a graph (ie: no repeated edges, possibly repeated vertices)

Explanation[edit]

This is a simple problem with a brute-force solution. There are only up to 25 nodes with up to 25 edges, so a brute-force approach will work fine.

For each vertex, perform a Depth-First Search on the graph. Find the longest trail you can traverse in this manner.

Input[edit]

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

Output[edit]

2
12

Solutions[edit]