Given a directed and connected graph with n nodes. If there is an edge from u to v then u depends on v. Our task was to find out the sum of dependencies for every node.
Example:
For the graph in diagram,
A depends on C and D i.e. 2
B depends on C i.e. 1
D depends on C i.e. 1
And C depends on none.
Hence answer -> 0 + 1 + 1 + 2 = 4
Asked in : Flipkart Interview
Idea is to check adjacency list and find how many edges are there from each vertex and return the total number of edges.
C++
// C++ program to find the sum of dependencies #include <bits/stdc++.h> using namespace std; // To add an edge void addEdge(vector <int> adj[], int u,int v) { adj[u].push_back(v); } // find the sum of all dependencies int findSum(vector<int> adj[], int V) { int sum = 0; // just find the size at each vector's index for (int u = 0; u < V; u++) sum += adj[u].size(); return sum; } // Driver code int main() { int V = 4; vector<int >adj[V]; addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 3); addEdge(adj, 2, 3); cout << "Sum of dependencies is " << findSum(adj, V); return 0; } |
Java
// Java program to find the sum of dependencies import java.util.Vector; class Test { // To add an edge static void addEdge(Vector <Integer> adj[], int u,int v) { adj[u].addElement((v)); } // find the sum of all dependencies static int findSum(Vector<Integer> adj[], int V) { int sum = 0; // just find the size at each vector's index for (int u = 0; u < V; u++) sum += adj[u].size(); return sum; } // Driver method public static void main(String[] args) { int V = 4; Vector<Integer> adj[] = new Vector[V]; for (int i = 0; i < adj.length; i++) { adj[i] = new Vector<>(); } addEdge(adj, 0, 2); addEdge(adj, 0, 3); addEdge(adj, 1, 3); addEdge(adj, 2, 3); System.out.println("Sum of dependencies is " + findSum(adj, V)); } } // This code is contributed by Gaurav Miglani |
Output:
Sum of dependencies is 4
Time complexity : O(V) where V is number of vertices in graph.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments