Pagini recente » Cod sursa (job #268332) | Cod sursa (job #45925) | Cod sursa (job #102962) | Cod sursa (job #3132393) | Cod sursa (job #1428340)
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
/*
* To change this license header, choose License Headers in Project Properties.
* To change this template file, choose Tools | Templates
* and open the template in the editor.
*/
/**
*
* @author sorin
*/
public class Main {
static Set<String> currentAvail = new HashSet<String>();
public static void main(String[] args) throws FileNotFoundException, UnsupportedEncodingException {
// Scanner scanner = new Scanner(new FileInputStream("darb.in"));
Scanner scanner = new Scanner(System.in);
Map<Integer,List<Integer>> graph = new HashMap<>();
int n = scanner.nextInt(); //Integer.valueOf(scanner.nextLine().trim());
for(int i = 0; i < n - 1; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
put(x,y,graph);
put(y,x,graph);
}
int farNode = bfs(n, graph, 1);
int distance = bfs(n, graph, farNode);
System.out.println(distance);
PrintWriter writer = new PrintWriter("darb.out", "UTF-8");
writer.println(distance);
writer.close();
}
private static int bfs(int n, Map<Integer, List<Integer>> graph,int toStart) {
LinkedList<Integer> nodes = new LinkedList<>();
nodes.addLast(toStart);
int max = 0;
int farthestNode = toStart;
int[] discoveryTimes = new int[n + 3];
discoveryTimes[toStart] = 1;
Set<Integer> traversed = new HashSet<>();
while(!nodes.isEmpty()){
int currentNode = nodes.pollFirst();
traversed.add(currentNode);
for (Integer node : graph.get(currentNode)) {
discoveryTimes[node] = discoveryTimes[currentNode] + 1;
if (discoveryTimes[node] > max) {
max = discoveryTimes[node];
farthestNode = node;
}
if (!traversed.contains(node)) {
nodes.addLast(node);
}
}
}
if (toStart == 1) return farthestNode;
else return max;
}
private static void put(int x, int y, Map<Integer, List<Integer>> graph) {
List<Integer> listRes = graph.get(x);
if (listRes == null) {
List<Integer> list = new ArrayList<>();
list.add(y);
graph.put(x, list);
} else {
listRes.add(y);
graph.put(x, listRes);
}
}
}