Cod sursa(job #1342984)

Utilizator bugyBogdan Vlad bugy Data 14 februarie 2015 18:54:20
Problema Diametrul unui arbore Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 1.92 kb
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;


class Tree {
	public int root;
	public ArrayList<ArrayList<Integer>> nodes = new ArrayList<ArrayList<Integer>>();

	public void setRoot(int rootData) {
		root = rootData;
	}
}

public class Main {

	public static Tree tree;
	public static int max, max1, val, index;
	
	public static void dfs(int node, int parent) {
		val++;
		if (val > max) {
			max = val;
			if (max > max1) {
				max1 = max;
				index = node;
			}
		}
		int len =  tree.nodes.get(node).size();
		for (int i = 0; i < len; i++) {
			int child = tree.nodes.get(node).get(i);
			if (child != parent) {
				dfs(child, node);
			}
		}
		val--;		
	}
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader bufferReader = new BufferedReader(new FileReader("darb.in"));
		
		int n = Integer.parseInt(bufferReader.readLine());
		
		tree = new Tree();
		
		for (int i = 0; i <= n+1; i++) {
			tree.nodes.add(new ArrayList<Integer>());
		}
		
		for (int i = 0; i < n-1; i++) {
			String[] numbers = bufferReader.readLine().split(" ");
			int x = Integer.parseInt(numbers[0]);
			int y = Integer.parseInt(numbers[1]);
			tree.nodes.get(x).add(y);
			tree.nodes.get(y).add(x);
		}
		bufferReader.close();
		
		tree.root = 1;
		int len = tree.nodes.get(tree.root).size();
		for (int i = 0; i < len; i++) {
			val = max = 0;
			dfs(tree.nodes.get(tree.root).get(i), tree.root);
		}
		len = tree.nodes.get(index).size();
		for (int i = 0; i < len; i++) {
			val = max = 0;
			dfs(tree.nodes.get(index).get(i), index);
			if (max > max1) {
				max1 = max;
			}
		}
			
		BufferedWriter fout = new BufferedWriter(new FileWriter("darb.out"));
		fout.write(Integer.toString(max1+1)+"\n");
		fout.close();
	}
}