1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 539 The Settlers Of Catan
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=480
*
* @author Stefan Burgmair
* @author YYY
* @version 1.0, 26/04/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.404
*/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main
{
static int longestWay = 0;
public static void main(String[] args) throws NumberFormatException, IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
do{
String[] input = reader.readLine().split(" ");
int n = Integer.parseInt(input[0]);
int m = Integer.parseInt(input[1]);
// -1 bedeutet: kein zweiter bzw. dritter Weg vorhandern
int[][] nodes = new int[n][3];
// true bedeutet: der weg wurde bereits genutzt
boolean[][] wayUsed = new boolean[n][3];

if(n != 0 && m != 0){
for (int i = 0; i < n; i++){
for (int j = 0; j < 3; j++){
nodes[i][j] = -1;
wayUsed[i][j] = false;
}
}

for (int i = 0; i < m; i++){
String[] arr = reader.readLine().split(" ");
int firstNode = Integer.parseInt(arr[0]);
int secondNode = Integer.parseInt(arr[1]);

if (nodes[firstNode][0] == -1)
nodes[firstNode][0] = secondNode;
else if (nodes[firstNode][1] == -1)
nodes[firstNode][1] = secondNode;
else
nodes[firstNode][2] = secondNode;

if (nodes[secondNode][0] == -1)
nodes[secondNode][0] = firstNode;
else if (nodes[secondNode][1] == -1)
nodes[secondNode][1] = firstNode;
else
nodes[secondNode][2] = firstNode;
}

for (int i = 0; i < n; i++){
findLongestWay(nodes, wayUsed, 0, i);
}

System.out.println(longestWay);
longestWay = 0;
}
}while (reader.ready());

}

public static void findLongestWay(int[][] nodes, boolean[][] wayUsed, int lengthOfWay, int node){
for (int i = 0; i < 3; i++){
if (wayUsed[node][i] == false && nodes[node][i] != -1){
wayUsed[node][i] = true;
for (int j = 0; j < 3; j++){
if (nodes[nodes[node][i]][j] == node){
wayUsed[nodes[node][i]][j] = true;
findLongestWay(nodes, wayUsed, lengthOfWay + 1, nodes[node][i]);
wayUsed[nodes[node][i]][j] = false;
}
}
wayUsed[node][i] = false;
}
}
if (longestWay < lengthOfWay)
longestWay = lengthOfWay;
}

--------------------------------------------------------
}




1.

package backtracking.settlersOfCatan;
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 539 Settlers of Catan
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=480
*
* @author Patrick Bédat
* @version 1.0, 19.12.2010
*
* Method : DP/Backtracking
* Status : Accepted
* Runtime: 0.488
*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;

public class Main
{

static HashMap<Integer, HashSet<Integer>> edges;
static int maxPath = 0;

public static void main(String... args) throws Exception
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

while (true)
{
int nNodes = 0;
int nEdges = 0;
StringTokenizer st = null;

st = new StringTokenizer(reader.readLine());
nNodes = Integer.parseInt(st.nextToken());
nEdges = Integer.parseInt(st.nextToken());

if (nNodes == 0 && nEdges == 0)
break;

edges = new HashMap<Integer, HashSet<Integer>>();

for (int i = 0; i < nEdges; i++)
{
st = new StringTokenizer(reader.readLine());

int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());

HashSet<Integer> neighbours = null;

if (edges.containsKey(from))
neighbours = edges.get(from);
else
{
neighbours = new HashSet<Integer>();
edges.put(from, neighbours);
}

neighbours.add(to);

if (edges.containsKey(to))
neighbours = edges.get(to);
else
{
neighbours = new HashSet<Integer>();
edges.put(to, neighbours);
}

neighbours.add(from);
}

ArrayList<Integer> path = new ArrayList<Integer>();

maxPath = 1;

for (int i = 0; i < nNodes; i++)
{
path.add(i);
findPath(i, 1, path);
path.clear();
}

System.out.println(maxPath - 1);
}
}

static void findPath(int currentNode, int pathLength, ArrayList<Integer> path)
{
maxPath = Math.max(pathLength, maxPath);

int currentIndex = path.indexOf(currentNode);
//traversed twice
if (path.get(0) != currentNode && currentIndex != pathLength - 1)
return;

//node not connected
if (!edges.containsKey(currentNode))
return;

for (Integer neighbour : edges.get(currentNode))
{
int neighbourIndex = path.indexOf(neighbour);

if(neighbourIndex > 0 && neighbourIndex < pathLength && path.get(neighbourIndex - 1) == currentNode)
continue;

if (pathLength > 1 && path.get(pathLength - 2) == neighbour)
continue;

if (path.size() > pathLength)
path.set(pathLength, neighbour);
else
path.add(neighbour);

findPath(neighbour, pathLength + 1, path);
}
}
}