Given a directed graph with V nodes and E edges. If there is an edge from u to v then u depends on v. Find out the sum of dependencies for every node. Duplicate edges should be counted as separate edges.
Example 1:
Input:
V=4
E=4
Edges={ {0,2},{0,3},{1,3},{2,3} }
Output:
4
Explanation:
For the graph in diagram, A depends
on C and D i.e. 2, B depends on D i.e.
1, C depends on D i.e. 1
and D depends on none.
Hence answer -> 0 + 1 + 1 + 2 = 4
Example 2:
Input:
V=4
E=3
Edges={ {0,3},{0,2},{0,1} }
Output:
3
Explanation:
The sum of dependencies=3+0+0+0=3.
Your Task:
You don't need to read input or print anything.Your task is to complete the function sumOfDependencies() which takes the adj (Adjacency list) and V (Number of nodes)as input parameters and returns the total sum of dependencies of all nodes.
Expected Time Complexity:O(V)
Expected Auxillary Space:O(1)
Constraints:
1<=V,E<=150
0<= Edges[i][0],Edges[i][1] <= V-1

Source: geeksforgeeks | Difficulty: EASY
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3

class Solution:
    def sumOfDependencies(self,adj,V):
        #code here

Solutions:
from collections import *

class Solution:

	def sumOfDependencies(self, adj, V):
		s = 0
		for i in range(V):
			s += len(adj[i])
		return s


class Solution:

	def sumOfDependencies(self, adj, V):
		res = 0
		for i in adj:
			res += len(i)
		return res


class Solution:

	def sumOfDependencies(self, adj, V):
		dep = 0
		for d in adj:
			dep += len(d)
		return dep


class Solution:

	def sumOfDependencies(self, adj, V):
		sum_of_dependencies = 0
		for i in range(len(adj)):
			sum_of_dependencies = sum_of_dependencies + len(adj[i])
		return sum_of_dependencies


class Solution:

	def sumOfDependencies(self, adj, V):
		ans = 0
		for i in range(V):
			for j in adj[i]:
				ans += 1
		return ans


class Solution:

	def sumOfDependencies(self, adj, V):
		total = 0
		for v in adj:
			total += len(v)
		return total


import collections

class Solution:

	def sumOfDependencies(self, adj, V):
		edges = collections.defaultdict(list)
		for i in range(V):
			edges[i] = adj[i]
		rSum = 0
		for i in range(V):
			rSum += len(edges[i])
		return rSum


class Solution:

	def sumOfDependencies(self, adj, V):
		c = 0
		for i in adj:
			for j in i:
				c += 1
		return c


class Solution:

	def sumOfDependencies(self, adj, V):
		output = 0
		for al in adj:
			output += len(al)
		return output


class Solution:

	def sumOfDependencies(self, adj, V):
		count = 0
		for row in adj:
			count += len(row)
		return count


class Solution:

	def sumOfDependencies(self, adj, V):
		return sum([len(adj[i]) for i in range(V)])


class Solution:

	def sumOfDependencies(self, adj, V):
		return sum((len(item) for item in adj))


class Solution:

	def sumOfDependencies(self, adj, V):
		total_deps = 0
		for node in range(V):
			total_deps += len(adj[node])
		return total_deps


class Solution:

	def sumOfDependencies(self, adj, V):
		sum = 0
		for elements in adj:
			sum = sum + len(elements)
		return sum


class Solution:

	def sumOfDependencies(self, adj, V):
		count = 0
		for i in adj:
			if len(i) > 0:
				count += len(i)
		return count


class Solution:

	def sumOfDependencies(self, adj, V):
		c = 0
		for h in adj:
			c += len(h)
		return c
		p = {}


class Solution:

	def sumOfDependencies(self, adj, V):
		ans = 0
		for x in adj:
			ans += len(x)
		return ans


from collections import defaultdict

class Solution:

	def sumOfDependencies(self, adj, V):
		adjacency = defaultdict(list)
		res = 0
		for edge in adj:
			res += len(edge)
		return res


class Solution:

	def sumOfDependencies(self, adj, v):
		s = 0
		for i in range(v):
			s += len(adj[i])
		return s


class Solution:

	def sumOfDependencies(self, adj, V):
		outdegree = [0] * V
		su = 0
		for i in range(0, V):
			for neigh in adj[i]:
				outdegree[i] += 1
		for i in range(0, V):
			su += outdegree[i]
		return su


class Solution:

	def sumOfDependencies(self, adj, V):
		if V <= 1:
			return V
		d = {}
		sum = 0
		for edge in adj:
			sum = sum + len(edge)
		return sum


class Solution:

	def sumOfDependencies(self, adj, V):
		sum1 = 0
		for u in range(V):
			sum1 += len(adj[u])
		return sum1


class Solution:

	def sumOfDependencies(self, adj, V):
		count = 0
		stack = []
		stack.append(0)
		for i in range(V):
			for j in range(len(adj[i])):
				count += 1
		return count


class Solution:

	def sumOfDependencies(self, x, V):
		return sum((len(i) for i in x))


class Solution:

	def sumOfDependencies(self, adj, V):
		count = 0
		n = len(adj)
		for i in range(n):
			count += len(adj[i])
		return count


class Solution:

	def sumOfDependencies(self, adj, V):
		count = 0
		for i in range(V):
			for child in adj[i]:
				count += 1
		return count


class Solution:

	def sumOfDependencies(self, adj, V):
		distinct_edges = 0
		for neighbours in adj:
			for neighbour in neighbours:
				distinct_edges += 1
		return distinct_edges