Pagini recente » Cod sursa (job #2034819) | Cod sursa (job #2764315) | Cod sursa (job #2844146) | Cod sursa (job #1402618) | Cod sursa (job #2197348)
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
public class Main {
public static void main(String[] args) throws FileNotFoundException {
Scanner scanner = new Scanner(new FileReader("darb.in"));
int n = scanner.nextInt();
Tree tree = new Tree(n);
while (scanner.hasNextInt()) {
tree.addEdge(scanner.nextInt()-1, scanner.nextInt()-1);
}
scanner.close();
PrintWriter printWriter = new PrintWriter("darb.out");
printWriter.print(tree.getDiameter());
printWriter.close();
}
}
class Tree {
List<Integer>[] adjList;
Tree(int size) {
if (size < 1) {
throw new IllegalArgumentException();
}
adjList = new List[size];
}
void addEdge(int s, int d) {
if (s < 0 || s >= adjList.length) {
throw new IllegalArgumentException("s should be greater or equal to zero");
}
if (d < 0 || d >= adjList.length) {
throw new IllegalArgumentException("d should be greater or equal to zero");
}
if (adjList[s] == null) {
adjList[s] = new LinkedList<>();
}
if (adjList[d] == null) {
adjList[d] = new LinkedList<>();
}
adjList[s].add(d);
adjList[d].add(s);
}
private int[] bfs(int s) {
int[] distances = new int[adjList.length];
Queue<Integer> queue = new LinkedList<>();
queue.offer(s);
while (!queue.isEmpty()) {
Integer node = queue.poll();
if (adjList[node] != null) {
for (Integer adjNode : adjList[node]) {
if (distances[adjNode] == 0) {
distances[adjNode] = distances[node]+1;
queue.offer(adjNode);
}
}
}
}
return distances;
}
int getFarthestElementFromRoot() {
int[] distances = bfs(0);
int maxNode = 0;
for (int i=1; i<distances.length; i++) {
if (distances[i] > distances[maxNode]) {
maxNode = i;
}
}
return maxNode;
}
int getFarthestDistanceFrom(int s) {
if (s < 0 || s >= adjList.length) {
throw new IllegalArgumentException("s should be greater or equal to zero");
}
int[] distances = bfs(s);
int maxDistance = distances[0];
for (int i=1; i<distances.length; i++) {
if (distances[i] > maxDistance) {
maxDistance = distances[i];
}
}
return maxDistance;
}
int getDiameter() {
int farthestNode = getFarthestElementFromRoot();
return getFarthestDistanceFrom(farthestNode)+1;
}
}