[DFS] Problem

You are given an unweighted, undirected tree. Write a program to output the length of the longest path (from one node to another) in that tree. The length of a path in this case is a number of edges we traverse from source to destination.

Input

The first line of the input file contains one integer N — — number of nodes in the tree (0 < N <= 10000). Next N-1 lines contain N-1 edges of that tree — — Each line contains a pair (u, v) means there is an edge between node u and node v (1 <= u, v <= N).

Output

Print the length of the longest path on one line.

Example

Input:
3
1 2
2 3
Output:
2

DFS Algorithms :-

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

#include <bits/stdc++.h>
using namespace std;
#define MAX 100009
bool check[MAX]={false};
int total=0;
int dfs(vector<int> v[],int root)
{
int m,m1=-1,m2=-1;
check[root]=1;
for(int i=0;i<v[root].size();i++)
{
if(!check[v[root][i]]){
m = dfs(v,v[root][i]);
if(m>=m1)
{
m2= m1;
m1 = m;
}
else if(m>m2)
m2=m;
}
}
total = max(total , m1+m2+2);
return (m1 + 1);
}
int main()
{
int n,a,b;
cin>>n;
vector<int> v[n+9];
for(int i=0;i<n-1;i++){
scanf(“%d%d”,&a,&b);
v[a].push_back(b);
v[b].push_back(a);
}
dfs(v,1);
cout<<total<<endl;
}

In java :-

import java.util.ArrayList;
import java.util.Scanner

public class LongestPath {

static int count=0;
static int max=0;
public static void main(String[] args) {

ArrayList<ArrayList<Integer>> adj = new ArrayList<>();
Scanner sc = new Scanner(System.in);
int n =sc.nextInt();
boolean visited[] = new boolean[10000000];

for(int i=0;i<=n;i++)
{
adj.add(new ArrayList<>());
}
for(int i=1;i<n;i++)
{
int u = sc.nextInt();
int v = sc.nextInt();
addEdge(adj,u,v);

}


dfs(1,visited,adj);

System.out.println(max);

}
public static void addEdge(ArrayList<ArrayList<Integer>> adj,int u ,int v)
{
adj.get(u).add(v);

}

public static void dfs(int node , boolean visited[],ArrayList<ArrayList<Integer>> adj)
{

visited[node]=true;
for(int it : adj.get(node))
{
if(!visited[it])
{
count++;

dfs(it,visited,adj);

if(max<count)
{
max=count;
}
count — ;




}

}

}
}