Find the Number of Nodes between two vertices in an Acyclic Graph using the Disjoint Union Method

Sample Testcase

Input

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

Output

3

Explanation

In the above test case, a total of 6 lines are given, therefore n=6. The first n-1 (5) lines are the connections between the vertices, and the nth or last line has the source vertex as 1 and the destination vertex as 3. From the below representation of the graph, it can be seen that there are 3 nodes: 4, 2, and 6 present between 1 and 3.

Approach

To be able to use the Disjoin Union Method, we need to first get the parent of each of the nodes of the given acyclic graph. To find the parent of each node breadth-first search can be used. For instance, if we start our breadth-first search from the source vertex (1), then 1 will be the parent of 4, 4 will be the parent of 5, 2 will be the parent of 6, and 6 will be the parent of 3.

To further find the number of nodes that are between the source and destination node, we can simply use a while loop whose starting point will be the parent of the destination node, and in every iteration, it gets updated with the parent of the current node, while simultaneously maintaining the count of the number of iterations using a count variable. This loop will run until we have reached the source node. Finally, the count variable will be our answer, representing the number of nodes between the source and destination node.

In our approach, the disjoint sets are all the sets with only a single vertex, and we have used the union operation for merging two sets where one contains the parent node and the other has the child node.

Code

C++ Code

#include <bits/stdc++.h>
using namespace std;

// a function to get the parents of each node
void getParents(vector<int> adj[], int n, vector<int> &parent, int src){
  
    // boolean array to keep track of unvisited nodes
    bool visited[n+1] = {0};
    
    queue<int> q;
    
    // start bfs from the source node 
    q.push(src);
    visited[src] = true;

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        
        // explore the neighbours of node u
        for (int i=0; i<adj[u].size(); ++i)
        {
            int v = adj[u][i];
            // if not visited
            if (!visited[v])
            {
                visited[v] = true;

                // since v is encountered through u
                // u becomes the parent of v
                parent[v] = u ;
                q.push(v);
            }
        }
    }
}

// a function to return the count
int countNodes (vector<int> adj[], int n, int src, int des){
    
    // parent array keeps track of the parent of each node
    vector<int> parent(n, -1);
    // get the parents
    getParents(adj, n, parent, src);
    
    // count variable to store the no. of iterations
    int count = 0;

    // loop starts with the parent of the des
    int i = parent[des];
    while (i != src)
    {
        count++;
        i = parent[i];
    }

    return count ;
}

int main()
{
    int V = 6;
    vector < int > adj[V + 1];

    // Constructing a graph
    adj[1].push_back(4);
    adj[4].push_back(1);
    adj[5].push_back(4);
    adj[4].push_back(5);
    adj[4].push_back(2);
    adj[2].push_back(4);
    adj[2].push_back(6);
    adj[6].push_back(2);
    adj[6].push_back(3);
    adj[3].push_back(6);
    
    cout << "The number of nodes between the source node: " << 1 << " and the destination node: " << 3 << " are " << countNodes(adj, 7, 1, 3);

    return 0;
}

Output:

The number of nodes between the source node: 1 and the destination node: 3 are 3

Java Code

// Java program to calculate the number
// of nodes between two nodes
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Vector;

public class CodingNinjas
{
    // function to get the parent of each node
    static void getParents(Vector<Integer> adj[],
                            int V, int src, int []parent)
    {
        
        // boolean array to keep track of unvisited nodes 
        Boolean visit[] = new Boolean[V + 1];

        //intialize
        Arrays.fill(visit, false);
        
        // a queue for bfs traversal
        Queue<Integer> q = new LinkedList<>();

        // start bfs from the source node 
        q.add(src);
        visit[src] = true;

        while(!q.isEmpty())
        {
            int u = q.peek();
            q.poll();
            for(int i=0; i < adj[u].size() ; ++i)
            {

                int v = adj[u].get(i);

                if(visit[v] != true )
                {
                    visit[v] = true;

                    // since v is encountered through u
                    // u becomes the parent of v
                    parent[v] = u;
                    q.add(v);
                }
            }
        }
    }
    
    static int countNodes(Vector<Integer> adj[],
                            int V, int src, int des)
    {
        // an array to store the parent of each node
        int parent[] = new int[V];
        // get the parent of each
        getParents(adj, V, src, parent);

        // count variable stores the no. of nodes in-between
        int count = 0;

        // loop starts with the parent of the des
        int i = parent[des];
        while(i != src)
        {
            count++;
            i = parent[i];
        }
        
        return count;
    }

    // Driver program to test the above function
    public static void main(String[] args)
    {
        int V = 6;
        Vector<Integer> adj[] = new Vector[V + 1];

        //Initializing Vector for each node
        for (int i = 0; i < V + 1; i++)       
            adj[i] = new Vector<>();       
        
        // constructing a graph
        adj[1].add(4);
        adj[4].add(1);
        adj[5].add(4);
        adj[4].add(5);
        adj[4].add(2);
        adj[2].add(4);
        adj[2].add(6);
        adj[6].add(2);
        adj[6].add(3);
        adj[3].add(6);

        System.out.println("The number of nodes between the source node: " + 1 + " and the destination node: " + 3 + " are " + countNodes(adj, 7, 1, 3));
    }
}

Output:

The number of nodes between the source node: 1 and the destination node: 3 are 3

Python Code

import queue

def getParents(adj, n, src, p):

    # to keep track of unvisited nodes
    visited = [0] * (n + 1)
    
    # a queue for bfs traversal
    q = queue.Queue()
    
    # start the bfs from src
    q.put(src)
    visited[src] = True

    while (not q.empty()):
        u = q.get()
        # explore the neighbors of node u
        for i in range(len(adj[u])):
            v = adj[u][i]
            if (not visited[v]):
                visited[v] = True
                # since v is encountered through u
                # u becomes the parent of v
                p[v] = u
                q.put(v)

# a function to return the count
def countNodes(adj, n, src, des):
    
    # parent array keeps track of the parent of each node
    parent = [None] * n
    # get the parents
    getParents(adj, n, src, parent)
    
    # count variable to store the no. of iterations
    count = 0

    # loop starts with the parent of the des
    i = parent[des]
    while (i != src):
        count += 1
        i = parent[i]

    return count

# Driver Code
if __name__ == '__main__':

    V = 6
    adj = [[] for i in range(V + 1)]
    
    # construcing graph
    adj[1].append(4)
    adj[4].append(1)
    adj[5].append(4)
    adj[4].append(5)
    adj[4].append(2)
    adj[2].append(4)
    adj[2].append(6)
    adj[6].append(2)
    adj[6].append(3)
    adj[3].append(6)

    print("The number of nodes between the source node: ", 1, " and the destination node: ", 3," are ", countNodes(adj, 7, 1, 3))

Output:

The number of nodes between the source node: 1 and the destination node: 3 are 3

Time Complexity: O(n), where n represents the number of nodes in the graph.

Frequently Asked Questions

Which traversal is used to find the shortest path?

The BFS is used to find the shortest path.

What is the time complexity of BFS?

The time complexity of BFS is O(V+E).

Which is faster in terms of speed: BFS or DFS?

DFS is faster in terms of speed than BFS.

Conclusion

In this article, we have extensively discussed the problem of finding the number of nodes between two vertices in an acrylic graph using the disjoint union method.

After reading about this problem, are you not feeling excited to read/explore more articles on Graph? Don’t worry; Coding Ninjas has you covered. To learn about the different types of graphs and applications, what is the difference between a graph and a tree, and what is breadth-first search.  

Check out this problem - Connect Nodes At Same Level

If you wish to enhance your skills in Data Structures and Algorithms, Competitive Programming, JavaScript, etc., you should check out our Guided path column at Code studio. We at Coding Ninjas Studio organize many contests in which you can participate. You can also prepare for the contests and test your coding skills by giving the mock test series available. In case you have just started the learning process, and your dream is to crack major tech giants like Amazon, Microsoft, etc., then you should check out the most frequently asked problems and the interview experiences of your seniors that will surely help you in landing a job in your dream company. 

Do upvote if you find the blogs helpful.

Happy Learning!