Cod sursa(job #1342974)

Utilizator bugyBogdan Vlad bugy Data 14 februarie 2015 18:45:28
Problema Diametrul unui arbore Scor 80
Compilator java Status done
Runda Arhiva educationala Marime 2.01 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;
import java.util.List;


class Tree {
	public int root;
	public Node nodes[];
	
	public void setRoot(int rootData) {
		root = rootData;
	}
}

class Node {
	public List<Integer> children = new ArrayList<Integer>(); 
}
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[node].children.size();
		for (int i = 0; i < len; i++) {
			int child = tree.nodes[node].children.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();
		tree.nodes = new Node[n+1];
		
		for (int i = 0; i <= n; i++) {
			tree.nodes[i] = new Node();
		}
		
		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[x].children.add(y);
			tree.nodes[y].children.add(x);
		}
		bufferReader.close();
		
		tree.root = 1;
		int len = tree.nodes[tree.root].children.size();
		for (int i = 0; i < len; i++) {
			val = max = 0;
			dfs(tree.nodes[tree.root].children.get(i), tree.root);
		}
		len = tree.nodes[index].children.size();
		for (int i = 0; i < len; i++) {
			val = max = 0;
			dfs(tree.nodes[index].children.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();
	}
}