Last Updated: 5 Mar, 2021

Sum of Dependencies in a Graph

Easy
Asked in company
Flipkart limited

Problem statement

You’re given a directed graph with 'V' nodes and 'E' edges. If there is an edge from node A to node B, then A depends on B. Your task is to find the sum of dependencies for every node.

Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.

Each test case’s first line contains two space-separated integers 'V' and 'E', denoting the graph’s nodes and edges, respectively.

The next ‘E’ line of each test case contains two space-separated integers X and Y, representing a directed edge from X to Y.
Output Format:
For every test case, print the sum of dependencies for every node.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function. 
Constraints:
1 <= T <= 5
1 <= V<= 10^4 
0 <= E <= V * (V-1)
0 <= X, Y <= V - 1

Time Limit: 1 sec

Approaches

01 Approach

Since the given graph is directed, each edge will represent a dependency from one node because if there is an edge from one node ‘X’ to another node ‘Y’, then we say that ‘X' depends on ‘Y. Hence the sum of dependencies will be equal to the total number of edges in the graph.