Cod sursa(job #3269386)

Utilizator lucky1992Ion Ion lucky1992 Data 18 ianuarie 2025 21:36:38
Problema Diametrul unui arbore Scor 60
Compilator java Status done
Runda Arhiva educationala Marime 2.93 kb
import java.io.*;
import java.util.*;

public class Main {

  public static class MyScanner implements Closeable {
    BufferedReader br;
    StringTokenizer st;

    public MyScanner(String file) throws FileNotFoundException {
      br = new BufferedReader(new InputStreamReader(new FileInputStream(file)), 1 << 16);
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String nextLine(){
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }
      return str;
    }

    @Override
    public void close() throws IOException {
      br.close();
    }
  }

  public static class UndirectedGraph {
    public int N;

    private List<Integer>[] adjList;

    public UndirectedGraph(int N) {
      this.N = N;
      adjList = (List<Integer>[])new List[N+1];
    }

    public void addEdge(int u, int v) {
      if (adjList[u] == null) {
        adjList[u] = new LinkedList<>();
      }

      if (adjList[v] == null) {
        adjList[v] = new LinkedList<>();
      }

      adjList[u].add(v);
      adjList[v].add(u);
    }

    public Collection<Integer> neighbors(int u) {
      if (adjList[u] == null) {
        return Collections.emptyList();
      } else {
        return adjList[u];
      }
    }
  }

  public static Queue<Integer> q = new LinkedList<>();
  public static int[] levels;

  public static int bfs(int u, UndirectedGraph g) {
    levels[u] = 1;
    q.add(u);

    int node = -1;

    while (!q.isEmpty()) {
      node = q.remove();

      for (int v : g.neighbors(node)) {
        if (levels[v] == 0) {
          levels[v] = levels[node] + 1;
          q.add(v);
        }
      }
    }

    return node;
  }

  public static void main(String[] args) throws IOException {
    try(MyScanner scanner = new MyScanner("darb.in");
        PrintWriter pw = new PrintWriter(new FileOutputStream("darb.out"))) {
      int N = scanner.nextInt();

      levels = new int[N+1];
      //Arrays.fill(levels, -1);
      UndirectedGraph g = new UndirectedGraph(N);

      for (int i = 1; i < N; i++) {
          g.addEdge(scanner.nextInt(), scanner.nextInt());
      }

      int leaf = bfs(1, g);

//      for (int i = 1; i <= N; i++) {
//        if (levels[i] == -1) {
//          leaf = bfs(i, g);
//          break;
//        }
//      }

      if (leaf == -1) {
        throw new IllegalStateException("leaf should not be -1!");
      }

      //Arrays.fill(levels, -1);

      levels = new int[N+1];

      int otherLeaf = bfs(leaf, g);

      pw.println(levels[otherLeaf]);
    }
  }
}