I am trying to solve https://www.spoj.com/problems/PT07Z/
My code is as follows:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;
public class LongestTreePath {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(reader.readLine());
Tree tree = new Tree(N);
for (int i = 0; i < N - 1; i++) {
StringTokenizer st = new StringTokenizer(reader.readLine());
int s = Integer.parseInt(st.nextToken()) - 1;
int d = Integer.parseInt(st.nextToken()) - 1;
tree.addEdge(s,d);
}
System.out.println(tree.path());
}
private static class Tree{
Node[] nodes;
Tree(int N){
nodes = new Node[N];
visited = new boolean[nodes.length];
for (int i = 0; i < N; i++) {
nodes[i] = new Node();
}
}
void addEdge(int s, int d){
nodes[s].edges.add(d);
nodes[d].edges.add(s);
}
int path(){
StackElement e = dfsPath(0);
Arrays.fill(visited, false);
e = dfsPath(e.nodeN);
return e.pathL;
}
private StackElement dfsPath(int n){
Stack<StackElement> stack = new Stack<>();
int pathLength = -1;
int endNode = -1;
for (int i = 0; i < nodes.length; i++) {
if (!visited[i]){
stack.push(new StackElement(i, -1));
while (!stack.empty()){
StackElement node = stack.pop();
if (visited[node.nodeN]){
continue;
}
visited[node.nodeN] = true;
if (node.pathL + 1 > pathLength){
pathLength = node.pathL + 1;
endNode = node.nodeN;
}
for (int x : nodes[node.nodeN].edges) {
stack.push(new StackElement(x, node.pathL+1));
}
}
}
}
return new StackElement(endNode, pathLength);
}
private final boolean[] visited;
}
private static class StackElement{
int nodeN;
int pathL;
StackElement(int n, int l){
nodeN = n;
pathL = l;
}
}
private static class Node{
ArrayList<Integer> edges;
Node(){
edges = new ArrayList<>();
}
}
}
What am I missing?
I am getting the longest path from node 0 and from that node I am running the search again.