Graph DFS

Solution.java

/**
 * @author: Aashish
 * Date: 13-07-2019
 */

import java.util.*;

class Solution {
    
    static class Graph {
        static Map<Integer, LinkedList<Integer>> adjVertices;
	
        public Graph(int vertices) {
            adjVertices = new HashMap<>();
        }
        
        public void addVertex(int star) {
            adjVertices.putIfAbsent(star, new LinkedList<>());
        }
        
        public void addEdge(int star1, int star2) {
            adjVertices.get(star1).add(star2);
        }

        public int dfs(int startStar, boolean[] visited) {
            visited[startStar-1] = true;
            Iterator<Integer> i = adjVertices.get(startStar).listIterator();
            while(i.hasNext()) {
                int n = i.next();
                if(!visited[n-1]) {
                    dfs(n, visited);
                }
            }
            //Return the farthest star
            return 1;
        }
    }
    
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        //input the number of test cases
        int numTestCases = scanner.nextInt();
        for(int i = 0; i < numTestCases; i++) {
            // Input the number of stars
            int noOfStars = scanner.nextInt();
            Graph graph = new Graph(noOfStars);
            for(int j = 0; j < noOfStars - 1; j++) {
                int startStar = scanner.nextInt();
                int endStar = scanner.nextInt();
                graph.addVertex(startStar);
                graph.addVertex(endStar);
                graph.addEdge(startStar, endStar);
            }
            // input the brightest star
            int brightestStar = scanner.nextInt();
            boolean[] visited = new boolean[noOfStars];
            int farthestStar = graph.dfs(brightestStar, visited);
            System.out.println(farthestStar);
        }
        scanner.close();
    }
}

Sample Input:

1
7
5 6
5 2
6 4
6 3
4 7
7 1
5

Sample Output:

1

Problem: Print the last element of the longest path from the start node of the graph