Cod sursa(job #1428337)

Utilizator sorin_olimpicoolSorin Olimpicu sorin_olimpicool Data 4 mai 2015 09:40:20
Problema Diametrul unui arbore Scor 0
Compilator java Status done
Runda Arhiva educationala Marime 2.28 kb
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);
        }
    }
 
}