Find the starting node in a directed graph which covers the maximum number of nodes

 Input: N = 5 1->2, 2->1, 3->1, 4->2, 5->3 

 Output: 5 Explanation: If we start from node 1 as beginning then the path is: 1 -> 2 If we start from node 2 as beginning then the path is: 2 -> 1 If we start from node 3 as beginning then the path is: 3 -> 1 -> 2 If we start from node 4 as beginning then the path is: 4 -> 2 -> 1 If we start from node 5 as beginning then path is: 5 -> 3 -> 1 -> 2 Hence, we can clearly see that if we start for 5, we cover the maximum number of nodes in the graph i.e. 4. 

 import java.util.HashSet; import java.util.Set; public class Main{ static int[] graph; // Driver Function public static void main(String[] args) { // Taking the number of nodes from the user int n = 5; // Array to store the nodes direction graph = new int[n]; // Initializing graph // 1->2, 2->1, 3->1, 4->2, 5->3 graph[0] = 1; graph[1] = 0; graph[2] = 0; graph[3] = 1; graph[4] = 2; System.out.println(find(n)); } static int find(int n) { int max = 0; // Holds the maximum count of nodes visited int node = 0; // Starting index of the node with maximum max count // Considering each node one-by-one as beginning node // Using DFS to fully explore that node for (int i = 0; i < n; i++) { // Finding the total number of node that can be covered by // considering the ith node as beginning int visits = canVisit(i); if (visits > max) { // If ith node covers more node then max = visits; // Store the number of nodes covered node = i; // Store the node index } } // As we are considering the indices from 0 just add 1 into the index return node + 1; // and return it } // Function to perform the DFS calculating the // count of the elements in a connected component static int canVisit(int n) { // This set contains the indices of the visited elements // This will help use to make sure that we are not running // inside a cycle in the graph Set<Integer> set = new HashSet<>(); set.add(n); // Add the current node into the graph as it is visited // Go to the next node in the graph towards with the current directs int visit = graph[n]; // Hold the total number of nodes visited // Since we at least visit the beginning node hence assign count to 1 int count = 1; // Explore until the node repeats or we reach at the dead-end while (!set.contains(visit)) { set.add(visit); // Add the next visit into the set visit = graph[visit]; // Jump to next directed node count++; // Increment the count as one more has been explored } return count; // Return the total number of nodes visited } }