Cod sursa(job #1429580)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 6 mai 2015 18:17:33
Problema Diametrul unui arbore Scor 90
Compilator java Status done
Runda Arhiva educationala Marime 3.49 kb
import java.io.FileInputStream;
import java.util.InputMismatchException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.FileOutputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author George Marcus
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream;
		try {
			inputStream = new FileInputStream("darb.in");
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
		OutputStream outputStream;
		try {
			outputStream = new FileOutputStream("darb.out");
		} catch (IOException e) {
			throw new RuntimeException(e);
		}
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		darb solver = new darb();
		solver.solve(1, in, out);
		out.close();
	}
}

class darb {
    int N;
    int[] Q;
    int[] distances;
    int[] end;
    int[] edges;
    int[] next;
    int crtEdgeIdx;

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        N = in.nextInt();
        edges = new int[2 * N];
        end = new int[2 * N];
        next = new int[2 * N];
        crtEdgeIdx = 1;
        for (int i = 0; i < N - 1; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            a--; b--;
            add(a, b);
            add(b, a);
        }
        Q = new int[N + 1];
        distances = new int[N + 1];
        int best1 = bfs(-1);
        int best2 = bfs(best1);

        out.println(distances[best2] - N);
    }

    private void add(int a, int b) {
        int crtEdge = crtEdgeIdx++;
        next[crtEdge] = end[a];
        end[a] = crtEdge;
        edges[crtEdge] = b;
    }

    private int bfs(int root) {
        int zero;
        if (root == -1) {
//            root = new Random().nextInt(N);
            root = 0;
            zero = 1;
        }
        else {
            zero = N + 1;
        }
        int p = 0;
        Q[p++] = root;
        distances[root] = zero;

        for (int i = 0; i < p; i++) {
            int node = Q[i];
            for (int j = end[node]; j != 0; j = next[j]) {
                int x = edges[j];
                if (distances[x] < zero) {
                    distances[x] = distances[node] + 1;
                    Q[p++] = x;
                }
            }
        }

        return Q[p - 1];
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int nextInt() {
        return Integer.parseInt(nextString());
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuffer res = new StringBuffer();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));

        return res.toString();
    }

    private boolean isSpaceChar(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

}