Spoj Problem PT07Z - Longest path in a tree [Java Solution]

   Spoj Problem PT07Z - Longest path in a tree[Java Solution]                                               using DFS

Problem Statement:-http://www.spoj.com/problems/PT07Z/

Hint:- Apply DFS two times.

To find the longest path in a tree apply a dfs algorithm two times.After first implication of DFS algo with any node assuming as a root and we get a deepest node of a tree and then from that node which we get from first applied DFS algo i.e. last visited node in DFS algo assume that node as a root of a tree.Then again apply a DFS with that node as a root and path from that node to the last node which we visted in second time DFS algo that path is a longest path in that tree.We can also do this task with the help of BFS algorithm(it should also be applied two times) . 

Java Program:-

/**

 * @(#)PT07Z.java

 *

 *

 * @author Suyash Bhalla

 * @version 1.00 2015/10/28

 */

import java.io.*;

import java.util.*;

class Node{

int label;

int level;

ArrayList<Node> hs;

Node(int label){

this.label=label;

hs=new ArrayList<Node>();

}

public void addAdj(Node u){

hs.add(u);

}

}

class PT07Z {

    public static void main(String args[])throws IOException{

   

    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

    int N=Integer.parseInt(br.readLine());

    Node all[]=new Node[N+1];

    visited=new int[N+1];

    ts=new TreeMap<>();

    for(int i=1;i<=N;i++){

    all[i]=new Node(i);

    }

    String temp[];

    for(int i=1;i<N;i++){

    temp=br.readLine().split(" ");

    int u=Integer.parseInt(temp[0]);

    int v=Integer.parseInt(temp[1]);

    all[u].addAdj(all[v]);

    all[v].addAdj(all[u]);

    }

    all[1].level=0;

    applyDFS(all[1]);

    Node t=ts.get(ts.lastKey());

    ts=new TreeMap<>();

    for(int i=1;i<=N;i++){

    all[i].level=0;

    visited[i]=0;

    }

    applyDFS(t);

    System.out.println(ts.lastKey());

    }

    static int visited[];

    static TreeMap<Integer,Node> ts;

    public static void applyDFS(Node n){

    //System.out.print(n.label+"("+n.level+") =>");

    visited[n.label]=1;

    Iterator it=n.hs.iterator();

    while(it.hasNext()){

    Node t=(Node)it.next();

    if(visited[t.label]==0){

    //System.out.print(t.label+" ");

    t.level=n.level+1;

    applyDFS(t);

    }

    //System.out.println();

    }

    ts.put(n.level,n);

    }

    

}

Input:-

3

1 2

2 3

Output:-

2

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------