_longestDistance-v1.java

public int longestDistanceI(int n, List<int[]> edges) {
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
        }
        // pick 0 as the root of this tree
        int[] result = new int[1];
        depthFirstSearch(adjacent, result, -1,0);
        return result[0] - 1;
    }

    public int[] depthFirstSearch(boolean[][] adjacent, int[] result, int parent, int node) {
        // return {pathWithRoot, pathWithoutRoot}
        int pathRoot = 1; // path started from root
        int path = 0; // path not started from root, may include
        int maxChildRoot = 0; // longest val that is from a child and started from that child root
        int secondMaxChildRoot = 0;

        for (int i = 0; i < adjacent[node].length; i++) {
            if (i != parent && adjacent[node][i]) {
                int[] childResult = depthFirstSearch(adjacent, result, node, i);
                path = Math.max(path, childResult[1]);
                if (childResult[0] >= maxChildRoot) {
                    secondMaxChildRoot = maxChildRoot;
                    maxChildRoot = childResult[0];
                } else if (childResult[0] > secondMaxChildRoot) {
                    secondMaxChildRoot = childResult[0];
                }
            }
        }

        pathRoot = 1 + maxChildRoot;
        // maxChildRoot + secondMaxChildRoot + 1
        path = Math.max(path, pathRoot + secondMaxChildRoot);
        result[0] = Math.max(result[0], Math.max(pathRoot, path));
        return new int[]{pathRoot, path};
    }

_longestDistance-v2.java

public int longestDistanceII(int n, List<int[]> edges) {
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
        }
        // pick 0 as a start node
        int[] res1 = breadFirstSearch(adjacent, 0, n);
        int[] res2 = breadFirstSearch(adjacent, res1[0], n);
        return res2[1] - 1;
    }

    public int[] breadFirstSearch(boolean[][] adjacent, int node, int n) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(node);
        int[] visited = new int[n]; // level count
        visited[node] = 1; // first level
        int maxLevel = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                maxLevel = Math.max(maxLevel, visited[curr]);
                for (int next = 0; next < n; next++) {
                    if (adjacent[curr][next] && visited[next] == 0) {
                        queue.offer(next);
                        visited[next] = visited[curr] + 1;
                    }
                }
            }
        }
        int endNode = -1;
        for (int i = 0; i < n; i++) {
            if (visited[i] == maxLevel) {
                endNode = i;
                break;
            }
        }
        return new int[]{endNode, maxLevel};
    }

_longestDistance-v3.java

public int longestDistanceIII(int n, List<int[]> edges) {
        int[] degree = new int[n];
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
            degree[edge[0]] += 1;
            degree[edge[1]] += 1;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        int step = 0;
        int count = n;
        while(count > 2) {
            Queue<Integer> queue2 = new LinkedList<>();
            step += 1;
            while(!queue.isEmpty()) {
                int curr = queue.poll();
                count -= 1;
                for (int k = 0; k < n; k++) {
                    if (adjacent[curr][k]) {
                        degree[k] -= 1;
                        if (degree[k] == 1) {
                            queue2.offer(k);
                        }
                    }
                }
            }
            queue.clear();
            queue = queue2;
        }
        return step * 2 + count - 1;
    }

LongestDistance.java

import org.junit.Assert;
import org.junit.Test;

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;

public class LongestDistance {
    class InputValues {
        int n;
        List<int[]> edges;
        public InputValues(int n, List<int[]> edges) {
            this.n = n;
            this.edges = edges;
        }
        @Override
        public String toString() {
            String res = "n: " + n + "\nedges:";
            for (int[] edge : edges) {
                res += Arrays.toString(edge) + "\t";
            }
            return res;
        }
    }

    @Test
    public void test() {
        File[] files = readFolder("src/input/LongestDistance");
        LongestDistance.InputValues test = readFile(files[3]);
        System.out.println(longestDistanceIII(test.n, test.edges));
    }

    @Test
    public void testAll() {
        File[] files = readFolder("src/input/LongestDistance");
        for (File file : files) {
            LongestDistance.InputValues test = readFile(file);
            int res1 = longestDistanceII(test.n, test.edges);
            int res2 = longestDistanceIII(test.n, test.edges);
            System.out.println("test: " + file.getName());
            System.out.println("res dfs: " + res1 + "\tres bfs: " + res2);
            Assert.assertEquals(res1, res2);
        }
    }

    
    public void generateOutput() throws IOException {
        File[] files = readFolder("src/input/LongestDistance");
        for (int i = 0; i < files.length; i++) {
            File file = files[i];
            String outfileName = "src/output/LongestDistance/" + file.getName().replace(".in", ".out");
            File outfile = new File(outfileName);
            outfile.getParentFile().mkdirs();
            outfile.createNewFile();
            PrintWriter printWriter = new PrintWriter(new FileWriter(outfileName));
            LongestDistance.InputValues test = readFile(file);
            int result = longestDistanceIII(test.n, test.edges);
            printWriter.println(result);
            printWriter.close();
        }
    }

    public int longestDistanceI(int n, List<int[]> edges) {
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
        }
        // pick 0 as the root of this tree
        int[] result = new int[1];
        depthFirstSearch(adjacent, result, -1,0);
        return result[0] - 1;
    }

    public int[] depthFirstSearch(boolean[][] adjacent, int[] result, int parent, int node) {
        // return {pathWithRoot, pathWithoutRoot}
        int pathRoot = 1; // path started from root
        int path = 0; // path not started from root, may include
        int maxChildRoot = 0; // longest val that is from a child and started from that child root
        int secondMaxChildRoot = 0;

        for (int i = 0; i < adjacent[node].length; i++) {
            if (i != parent && adjacent[node][i]) {
                int[] childResult = depthFirstSearch(adjacent, result, node, i);
                path = Math.max(path, childResult[1]);
                if (childResult[0] >= maxChildRoot) {
                    secondMaxChildRoot = maxChildRoot;
                    maxChildRoot = childResult[0];
                } else if (childResult[0] > secondMaxChildRoot) {
                    secondMaxChildRoot = childResult[0];
                }
            }
        }

        pathRoot = 1 + maxChildRoot;
        // maxChildRoot + secondMaxChildRoot + 1
        path = Math.max(path, pathRoot + secondMaxChildRoot);
        result[0] = Math.max(result[0], Math.max(pathRoot, path));
        return new int[]{pathRoot, path};
    }

    public int longestDistanceII(int n, List<int[]> edges) {
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
        }
        // pick 0 as a start node
        int[] res1 = breadFirstSearch(adjacent, 0, n);
        int[] res2 = breadFirstSearch(adjacent, res1[0], n);
        return res2[1] - 1;
    }

    public int[] breadFirstSearch(boolean[][] adjacent, int node, int n) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(node);
        int[] visited = new int[n]; // level count
        visited[node] = 1; // first level
        int maxLevel = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curr = queue.poll();
                maxLevel = Math.max(maxLevel, visited[curr]);
                for (int next = 0; next < n; next++) {
                    if (adjacent[curr][next] && visited[next] == 0) {
                        queue.offer(next);
                        visited[next] = visited[curr] + 1;
                    }
                }
            }
        }
        int endNode = -1;
        for (int i = 0; i < n; i++) {
            if (visited[i] == maxLevel) {
                endNode = i;
                break;
            }
        }
        return new int[]{endNode, maxLevel};
    }

    public int longestDistanceIII(int n, List<int[]> edges) {
        int[] degree = new int[n];
        boolean[][] adjacent = new boolean[n][n];
        for (int[] edge : edges) {
            adjacent[edge[0]][edge[1]] = true;
            adjacent[edge[1]][edge[0]] = true;
            degree[edge[0]] += 1;
            degree[edge[1]] += 1;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        int step = 0;
        int count = n;
        while(count > 2) {
            Queue<Integer> queue2 = new LinkedList<>();
            step += 1;
            while(!queue.isEmpty()) {
                int curr = queue.poll();
                count -= 1;
                for (int k = 0; k < n; k++) {
                    if (adjacent[curr][k]) {
                        degree[k] -= 1;
                        if (degree[k] == 1) {
                            queue2.offer(k);
                        }
                    }
                }
            }
            queue.clear();
            queue = queue2;
        }
        return step * 2 + count - 1;
    }

    private int getInt(String name) {
        return Integer.parseInt(name.replaceAll("\\D", ""));
    }

    private File[] readFolder(String path) {
        File folder = new File(path);
        File[] files = folder.listFiles();
        Arrays.sort(files, (a, b) -> getInt(a.getName()) - getInt(b.getName()));
        return files;
    }

    private LongestDistance.InputValues readFile(File file) {
        try {
            // assume the input file is always valid
            Scanner sc = new Scanner(file);
            List<int[]> edges = new ArrayList<>();
            int n = Integer.parseInt(sc.nextLine().trim());
            while(sc.hasNextLine()){
                String[] vertices = sc.nextLine().split(" ");
                int[] edge = new int[2];
                edge[0] = Integer.parseInt(vertices[0]);
                edge[1] = Integer.parseInt(vertices[1]);
                edges.add(edge);
            }
            sc.close();
            return new LongestDistance.InputValues(n, edges);
        } catch (FileNotFoundException e) {
            System.out.println(file.getName() + " not exist");
        }
        return null;
    }
}