In this article, we will discuss about finding the number of nodes between two vertices in an acrylic graph using the disjoint union method problem, along with a sample test case and an approach to solve the problem.

Problem Statement

We are given a Connected Acyclic Graph, a Source vertex, and a Destination vertex. We need to find the number of vertices that are between the source and destination vertex using the Disjoint Union Method.

Input Format

Given â€˜nâ€™ lines, where the first â€˜n-1â€™ lines are the connection between the vertices. And in the â€˜nthâ€™ line, the source vertex and destination vertex are given.

Output Format

Return an Integer Value representing the number of vertices between the source and destination vertex.

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.

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.