Cod sursa(job #2197348)

Utilizator ibicecIT Zilla ibicec Data 21 aprilie 2018 20:58:20
Problema Diametrul unui arbore Scor 40
Compilator java Status done
Runda Arhiva educationala Marime 2.87 kb
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;
    }

}