Wednesday, June 10, 2015

UVa 539 - The Settlers of Catan

// UVa 539 - The Settlers of Catan

import java.util.*;

public class Main {

	static int n;
	static int m;
	static boolean[][] link = new boolean[100][100];

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		m = sc.nextInt();

		while (n != 0 && m != 0) {

			for (int i = 0; i < n; i++)
				for (int j = 0; j < n; j++) {
					link[i][j] = false;
				}

			for (int j = 0; j < m; j++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				link[a][b] = true;
				link[b][a] = true;
			}

			int sol = 0;
			for (int i = 0; i < n; i++) {
				int c = lvl(i);
				if (sol < c)
					sol = c;
			}

			System.out.println(sol - 1);
			n = sc.nextInt();
			m = sc.nextInt();
		}

	}

	public static int lvl(int k) {
		int max = 0;
		for (int l = 0; l < n; l++)
			if (link[k][l]) {
				link[k][l] = false;
				link[l][k] = false;
				int z = lvl(l);
				if (z > max)
					max = z;
				link[k][l] = true;
				link[l][k] = true;
			}
		return max + 1;
	}

}

No comments:

Post a Comment