Sum of Dependencies in a Graph

Easy

0/40

Average time to solve is 20m

Contributed by

1 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1:

Sample Output 1:

Explanation of Sample Input 1:

In the first test case, 0 depends on 1 and 2. 1 depends on 2. Hence the sum of dependencies is 2 + 1 = 3

Sample Input 2:

Sample Output 2:

Explanation of Sample Input 2:

In the first test case, 0 depends on 1, 2, and 3. 1 depends on 2 and 3 and 2 depends on 3. Hence the sum of dependencies is  3 + 2 + 1 = 6

Hint 1

Can you try to check how many edges are there from each node?

Approaches (1)

Approach 1

Implementation

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.

Time Complexity

O(1).

Because, as we are not using any extra time.

Space Complexity

O(1).

Because, as we are not using any extra space.

(100% EXP penalty)

Sum of Dependencies in a Graph

Console