DEV Community

loading...
Cover image for Find the starting node in a directed graph which covers the maximum number of nodes

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

sumit profile image Sumit Singh 惻Updated on 惻3 min read

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
Enter fullscreen mode Exit fullscreen mode

Graph Structure:
Alt Text

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.
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Discussion

pic
Editor guide
Collapse
thejscode profile image
Jaskirat Grewal

Nice Post!
Use #beginner to make sure that it reaches more people in the learning domain.

Collapse
thejscode profile image
Jaskirat Grewal

Also #tutorial should be used as you have provided step by step implementation.

Collapse
sumit profile image
Sumit Singh Author

Thanks mate...

Collapse
ubaid77 profile image
Mohammad Ubaid

arrayoutofbounds error for node 3 3 1

Collapse
anxious_morty profile image
Deepak Rawte

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;

Collapse
sumit profile image
Sumit Singh Author

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.