forked from Haresh1204/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
/
calculate number of nodes dfs method.txt
87 lines (67 loc) · 1.66 KB
/
calculate number of nodes dfs method.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of nodes
// in the path from source to destination
int dfs(int src, int dest, int* vis,
vector<int>* adj)
{
// Mark the node visited
vis[src] = 1;
// If dest is reached
if (src == dest) {
return 1;
}
// Traverse all adjacent nodes
for (int u : adj[src]) {
// If not already visited
if (!vis[u]) {
int temp = dfs(u, dest, vis, adj);
// If there is path, then
// include the current node
if (temp != 0) {
return temp + 1;
}
}
}
// Return 0 if there is no path
// between src and dest through
// the current node
return 0;
}
// Function to return the
// count of nodes between two
// given vertices of the acyclic Graph
int countNodes(int V, int E, int src, int dest,
int edges[][2])
{
// Initialize an adjacency list
vector<int> adj[V + 1];
// Populate the edges in the list
for (int i = 0; i < E; i++) {
adj[edges[i][0]].push_back(edges[i][1]);
adj[edges[i][1]].push_back(edges[i][0]);
}
// Mark all the nodes as not visited
int vis[V + 1] = { 0 };
// Count nodes in the path from src to dest
int count = dfs(src, dest, vis, adj);
// Return the nodes between src and dest
return count - 2;
}
// Driver Code
int main()
{
// Given number of vertices and edges
int V = 8, E = 7;
// Given source and destination vertices
int src = 5, dest = 2;
// Given edges
int edges[][2]
= { { 1, 4 }, { 4, 5 },
{ 4, 2 }, { 2, 6 },
{ 6, 3 }, { 2, 7 },
{ 3, 8 } };
cout << countNodes(V, E, src, dest, edges);
return 0;
}