## DEV Community Sumit Singh

Posted on • Updated on

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

Given a directed graph with N number of nodes and exactly N number of edges. Each node has exactly one outgoing edge from it. Find a path such that the maximum number of nodes can be covered from the starting point, and return the starting point.

`NOTE: A node can have multiple edges which are pointing towards him, but only one outgoing edge`

``````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.
``````

Approach:

To find the number of nodes reachable from a particular node, one thing to observe is that we can reach from a node X to a node Y only when they are in the same connected component.

Since the graph is directional, any node in a connected component to any other node in the same connected components. Hence for a particular node X number of nodes that will be reachable will be the number of nodes in that particular component. Use a depth-first search to find the answer.

CODE
Following is a `Java` implementation of the code:

``````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 = 1;
graph = 0;
graph = 0;
graph = 1;
graph = 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)) {
count++; // Increment the count as one more has been explored
}

return count; // Return the total number of nodes visited
}
}

``````

Complexity:

We will have the worst case if the graph is linearly connected with no internal cycles, which will give us `O(N²)`. With an Auxiliary space of `O(N)`. Nice Post!
Use #beginner to make sure that it reaches more people in the learning domain. Also #tutorial should be used as you have provided step by step implementation. Sumit Singh

Thanks mate... Sumit Singh

On my machine, the test case you have given is working fine. It would be very beneficial if you can just attach a screenshot of what you have tried.