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

Graph Structure:

``````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[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
}
}

``````

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

arrayoutofbounds error for node 3 3 1

Just because indices must be changed to 2 2 0, just copying code won't work :) in challenges. if using static -----> do arr[i] = B[i]-1;

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.