Pagini recente » Cod sursa (job #2584169) | Cod sursa (job #1391877) | Cod sursa (job #502864) | Cod sursa (job #68824) | Cod sursa (job #1428337)
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
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; i++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
put(x,y,graph);
put(y,x,graph);
}
int farNode = bfs(n, graph, 1);
PrintWriter writer = new PrintWriter("darb.out", "UTF-8");
writer.println(bfs(n, graph, farNode));
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+1];
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);
}
}
}