Given a Directed Graph having V nodes numbered from 0 to V-1, and E directed edges. Given two nodes, source and destination, count the number of ways or paths between these two vertices in the directed graph. These paths should not contain any cycle.
Note: Graph doesn't contain multiple edges, self-loop, and cycles.
Example 1:
Input:
V = 5, E = 7
Edges of Graph = 
{0, 1}
{0, 2}
{0, 4}
{1, 3}
{1, 4}
{2, 4}
{3, 2}
source = 0 
destination = 4
Output: 4
Explanation: 
There are 4 paths from 0 to 4.
0 -> 4
0 -> 1 -> 4
0 -> 2 -> 4
0 -> 1 -> 3 -> 2 -> 4
Example 2:
Input:
V = 4, E = 5
Edges of Graph = 
{0, 1}
{0, 3}
{1, 2}
{1, 3}
{2, 3}
source = 0 
destination = 3
Output: 3
Explanation:
There are 3 paths from 0 to 3.
0 -> 3
0 -> 1 -> 3
0 -> 1 -> 2 -> 3
Your task:
You don't need to read, input, or print anything. Your task is to complete the function countPaths(), which takes the integer V denoting the number of vertices, adjacency list adj, integer source, and destination as input parameters and returns the number of paths in the graph from the source vertex to the destination vertex.
Expected Time Complexity: O(V!)
Expected Auxiliary Space: O(V)
Constraints:
1 ≤ V, E ≤ 100
1 ≤ source, destination ≤ V

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    

    #Function to count paths between two vertices in a directed graph.

    def countPaths(self, V, adj, source, destination):

        # code here

Solutions:
class Solution:

	def countPaths(self, V, adj, source, destination):
		sum_paths = 0
		if source == destination:
			return 1
		for child in adj[source]:
			sum_paths += self.countPaths(V, adj, child, destination)
		return sum_paths


c = 0

class Solution:

	def dfs(self, adj, u, dest, vis, c):
		vis[u] = True
		if u == dest:
			c[0] += 1
		else:
			for v in adj[u]:
				if vis[v] == False:
					self.dfs(adj, v, dest, vis, c)
		vis[u] = False

	def countPaths(self, V, adj, source, destination):
		vis = [False] * V
		c = [0]
		self.dfs(adj, source, destination, vis, c)
		return c[0]


class Solution:

	def dfs(self, node, d, graph):
		if node == d:
			self.ans += 1
			return
		self.visited[node] = 1
		for i in graph[node]:
			if not self.visited[i]:
				self.dfs(i, d, graph)
		self.visited[node] = 0

	def countPaths(self, V, adj, source, destination):
		self.visited = [0] * V
		self.ans = 0
		self.dfs(source, destination, adj)
		return self.ans


class Solution:

	def countPaths(self, V, adj, source, destination):
		self.co = 0
		vis = {source}
		self.dfsPth(source, destination, adj, vis)
		return self.co

	def dfsPth(self, v, dest, adj, vis):
		if dest == v:
			self.co += 1
			return
		for ad in adj[v]:
			if ad not in vis:
				vis.add(ad)
				self.dfsPth(ad, dest, adj, vis)
				vis.remove(ad)


class Solution:
	cnt = 0

	def countPaths(self, V, adj, src, des):

		def dfs(node, des, adj, visited):
			if node == des:
				Solution.cnt += 1
				return
			for u in adj[node]:
				if visited[u] == False:
					visited[u] = True
					dfs(u, des, adj, visited)
					visited[u] = False
		Solution.cnt = 0
		visited = [False for _ in range(V)]
		dfs(src, des, adj, visited)
		return Solution.cnt


class Solution:

	def __init__(self):
		self.V = None
		self.graph = None

	def find_all_path(self, start, end, path=[]):
		path = path + [start]
		if start == end:
			return [path]
		paths = []
		for node in self.graph[start]:
			sub_routes = self.find_all_path(node, end, path)
			for route in sub_routes:
				paths.append(route)
		return paths

	def countPaths(self, V, adj, source, destination):
		self.V = V
		self.graph = adj
		paths = self.find_all_path(source, destination)
		return len(paths)


class Solution:

	def countPaths(self, V, adj, source, destination):

		def dfs(adj, s, des):
			if s == des:
				return 1
			y = 0
			for i in adj[s]:
				y = y + dfs(adj, i, des)
			return y
		return dfs(adj, source, destination)


class Solution:

	def f(self, root, dest, vis, adj, count, w):
		if root == dest:
			count[0] += 1
			return 1
		if vis[root] == 1:
			count[0] += w[root]
			return w[root]
		vis[root] = 1
		for i in adj[root]:
			w[i] = self.f(i, dest, vis, adj, count, w)
			w[root] += w[i]
		return w[root]

	def countPaths(self, V, adj, source, destination):
		count = [0]
		vis = [0] * V
		w = [0] * V
		self.f(source, destination, vis, adj, count, w)
		return count[0]


from collections import deque

class Solution:

	def countPaths(self, V, adj, source, destination):
		q = deque([source])
		res = 0
		while q:
			cur = q.popleft()
			if cur == destination:
				res += 1
			for nei in adj[cur]:
				q.append(nei)
		return res


class Solution:

	def util(self, V, adj, source, destination, count, path=[]):
		path.append(source)
		if source == destination:
			return count + 1
		for neighbor in adj[source]:
			count = self.util(V, adj, neighbor, destination, count, path)
			path.pop(-1)
		return count

	def countPaths(self, V, adj, source, destination, count=0):
		res = self.util(V, adj, source, destination, count)
		return res


class Solution:

	def countPaths(self, V, adj, source, destination):
		l = [0]

		def f(s):
			if s == destination:
				l[0] += 1
				return
			for i in adj[s]:
				f(i)
		f(source)
		return l[0]


class Solution:

	def countPaths(self, V, adj, source, destination):
		paths = [-1 for i in range(V)]
		paths[destination] = 1
		recStack = [False for i in range(V)]
		return self.dfsUtil(source, adj, recStack, paths)

	def dfsUtil(self, u, adj, recStack, paths):
		if paths[u] != -1:
			return paths[u]
		recStack[u] = True
		count = 0
		for v in adj[u]:
			if not recStack[v]:
				count += self.dfsUtil(v, adj, recStack, paths)
		paths[u] = count
		recStack[u] = False
		return paths[u]


class Solution:

	def dfs(self, adj, node, destination, visited, count):
		if node == destination:
			visited.remove(destination)
			count[0] += 1
			return
		for neighbour in adj[node]:
			if neighbour not in visited:
				visited.append(neighbour)
				self.dfs(adj, neighbour, destination, visited, count)
		visited.remove(node)

	def countPaths(self, V, adj, source, destination):
		count = [0]
		visited = [source]
		self.dfs(adj, source, destination, visited, count)
		return count[0]


def countPaths(graph, u, v, visit, counter):
	if u == v:
		return 1
	if u in visit:
		return 0
	if counter[u] != -1:
		return counter[u]
	visit.add(u)
	paths = 0
	for u_ in graph[u]:
		paths += countPaths(graph, u_, v, visit, counter)
	visit.remove(u)
	counter[u] = paths
	return paths

class Solution:

	def countPaths(self, V, adj, source, destination):
		graph = {u: set() for u in range(V)}
		counter = {u: -1 for u in range(V)}
		return countPaths(adj, source, destination, set(), counter)


from collections import deque

class Solution:

	def countPaths(self, V, adj, source, destination):
		return self.func(adj, source, destination)

	def func(self, adj, source, destination):
		q = deque()
		q.append((source, set([source])))
		count = 0
		while q:
			(tnode, visited) = q.popleft()
			if tnode == destination:
				count += 1
				continue
			for i in adj[tnode]:
				if i not in visited:
					q.append((i, visited | set([i])))
		return count


class Solution:

	def countPaths(self, V, adj, source, destination):

		def dfs(d, node, des, vis):
			if node == des:
				self.c += 1
				vis[node] = False
				return
			for ne in d[node]:
				if vis[ne] == False:
					dfs(d, ne, des, vis)
			vis[node] = False
		d = {}
		visited = {}
		for i in range(V):
			visited[i] = False
		self.c = 0
		dfs(adj, source, destination, visited)
		return self.c


class Solution:

	def countPaths(self, n, x, src, dest):

		def f(i):
			if i == dest:
				return 1
			if dp[i] != None:
				return dp[i]
			ans = 0
			for j in x[i]:
				ans += f(j)
			dp[i] = ans
			return ans
		dp = [None for i in range(n)]
		return f(src)


class Solution:

	def countPaths(self, V, adj, source, destination):
		return self.helper(source, adj, destination, set())

	def helper(self, node, edges, end, visited):
		if node == end:
			return 1
		output = 0
		visited = visited.copy()
		visited.add(node)
		for item in edges[node]:
			output += self.helper(item, edges, end, visited)
		return output


class Solution:

	def countPaths(self, V, adj, source, destination):
		paths = [0]
		visited = set()
		self.dfs(adj, source, destination, visited, paths)
		return paths[0]

	def dfs(self, graph, src, dest, visited, paths):
		visited.add(src)
		if src == dest:
			paths[0] += 1
		else:
			for adj in graph[src]:
				if adj not in visited:
					self.dfs(graph, adj, dest, visited, paths)
		visited.remove(src)


class Solution:

	def __init__(self):
		self.cnt = 0

	def countPaths(self, V, adj, source, destination):
		visited = set()

		def dfs(node):
			if node == destination:
				self.cnt += 1
				return
			for edg in adj[node]:
				if edg in visited:
					continue
				visited.add(edg)
				dfs(edg)
				visited.remove(edg)
		dfs(source)
		return self.cnt


class Solution:

	def countPaths(self, V, adj, source, destination):
		return dfs(source, adj, destination, set())

def dfs(n, g, d, v):
	if n == d:
		return 1
	cnt = 0
	for nei in g[n]:
		if nei not in v:
			v.add(nei)
			cnt += dfs(nei, g, d, v)
			v.remove(nei)
	return cnt


class Solution:

	def dfs(self, adj, src, des):
		if src == des:
			return 1
		count = 0
		for i in adj[src]:
			count += self.dfs(adj, i, des)
		return count

	def countPaths(self, V, adj, source, destination):
		return self.dfs(adj, source, destination)


class Solution:

	def countPaths(self, V, adj, source, destination):
		return self.helper(adj, source, destination)

	def helper(self, adj, node, destination):
		summ = 0
		if node == destination:
			return 1
		for i in adj[node]:
			summ += self.helper(adj, i, destination)
		return summ


class Solution:

	def countPaths(self, V, adj, source, destination):
		curr = source
		count = self.f(V, adj, source, destination, curr)
		return count

	def f(self, V, adj, source, destination, curr):
		if curr == destination:
			return 1
		count = 0
		for node in adj[curr]:
			count += self.f(V, adj, source, destination, node)
		return count


class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = [False for i in range(V)]
		return self.dfs(source, adj, visited, destination)

	def dfs(self, node, adj, visited, target):
		if node == target:
			return 1
		if visited[node]:
			visited[node] = False
			return 0
		visited[node] = True
		output = 0
		for i in adj[node]:
			output += self.dfs(i, adj, visited, target)
		visited[node] = False
		return output


def dfs(graph, v, visited, d):
	if v == d:
		return 1
	visited[v] = True
	c = 0
	for i in graph[v]:
		if not visited[i]:
			c += dfs(graph, i, visited, d)
	visited[v] = False
	return c

class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = [0] * V
		return dfs(adj, source, visited, destination)


class Solution:

	def countPaths(self, V, adj, source, destination):
		counter = []
		walkGraph(V, adj, source, destination, [source], counter)
		return len(counter)

def walkGraph(V, adj, source, destination, paths, counter):
	if paths[-1] == destination:
		counter.append(paths)
		return
	for i in adj[source]:
		paths.append(i)
		walkGraph(V, adj, i, destination, paths, counter)
		paths.pop()
	return


class Solution:

	def countPaths(self, V, adj, source, destination):
		lis = [source]
		count = []
		cPaths(V, adj, source, destination, lis, count)
		return len(count)

def cPaths(V, adj, source, destination, lis, count):
	if lis[-1] == destination:
		count.append(lis)
		return
	for el in adj[source]:
		lis.append(el)
		cPaths(V, adj, el, destination, lis, count)
		lis.pop()
	return


class Solution:

	def countPaths(self, V, adj, source, destination):
		sol = []
		percorso = [source]
		self.countPaths_solver(V, adj, source, destination, percorso, sol)
		return len(sol)

	def countPaths_solver(self, V, adj, source, destination, percorso, sol):
		if percorso[-1] == destination:
			sol.append(percorso)
			return
		for i in adj[source]:
			percorso.append(i)
			self.countPaths_solver(V, adj, i, destination, percorso, sol)
			percorso.pop()


class Solution:

	def countPaths(self, V, adj, source, destination):
		ans = [0] * 1
		if source == destination:
			ans[0] += 1

		def dfs(adj, s):
			for i in adj[s]:
				if i == destination:
					ans[0] += 1
				else:
					dfs(adj, i)
		for i in adj[source]:
			if i == destination:
				ans[0] += 1
			else:
				dfs(adj, i)
		return ans[0]


class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = []
		for i in range(V):
			visited.append(0)

		def recursion(mat, ans, s):
			visited[s] = 1
			if s == destination:
				ans[0] += 1
			else:
				for i in mat[s]:
					if visited[i] == 0:
						recursion(mat, ans, i)
			visited[s] = 0
		mat = dict()
		count = 0
		for i in adj:
			mat[count] = i
			count += 1
		ans = [0]
		recursion(mat, ans, source)
		return ans[0]


class Solution:

	def dfs(self, node, dest, visited, adj, count):
		visited[node] = True
		if node == dest:
			count[0] += 1
			visited[node] = False
			return
		for neighbor in adj[node]:
			if visited[neighbor] != True:
				self.dfs(neighbor, dest, visited, adj, count)
		visited[node] = False

	def countPaths(self, V, adj, source, destination):
		visited = [False] * V
		count = [0]
		self.dfs(source, destination, visited, adj, count)
		return count[0]


class Solution:
	ans = 0

	def dfs(self, u, adj, destination, vis):
		vis[u] = True
		if u == destination:
			self.ans += 1
		for i in adj[u]:
			if vis[i] == False:
				self.dfs(i, adj, destination, vis)
		vis[u] = False

	def countPaths(self, V, adj, source, destination):
		vis = [False for i in range(V)]
		self.dfs(source, adj, destination, vis)
		return self.ans


def countPathsHelper(V, adj, source, destination, n, visited, st):
	st.append(source)
	for i in adj[source]:
		if i == destination:
			n[0] += 1
		elif i not in st:
			countPathsHelper(V, adj, i, destination, n, visited, st)
	st.pop()

class Solution:

	def countPaths(self, V, adj, source, destination):
		if source == destination:
			return 1
		visited = [False] * V
		n = [0]
		st = []
		countPathsHelper(V, adj, source, destination, n, visited, st)
		return n[0]


class Solution:

	def dfs(self, node, adj, path, ans, target):
		path.append(node)
		if node == target:
			ans.append(list(path))
		for v in adj[node]:
			self.dfs(v, adj, path, ans, target)
		path.pop()

	def countPaths(self, V, adj, source, destination):
		ans = []
		self.dfs(source, adj, [], ans, destination)
		return len(ans)


class Solution:

	def countPaths(self, V, adj, source, destination):

		def dfs(i, cur, destination):
			if i == destination:
				result.append(cur[:])
				return
			for j in adj[i]:
				dfs(j, cur + [j], destination)
		nodes = V
		result = []
		dfs(source, [0], destination)
		return len(result)


class Solution:
	nofways = 0

	def countPaths(self, V, adj, s, d):
		self.Dfs(s, adj, d)
		return self.nofways

	def Dfs(self, i, adj, d):
		if i == d:
			self.nofways += 1
			return
		for j in adj[i]:
			self.Dfs(j, adj, d)


class Solution:

	def countPaths(self, V, adj, source, destination):
		q = []
		q.append(source)
		ans = 0
		if source == destination:
			ans += 1
		while q:
			node = q.pop(0)
			for i in adj[node]:
				if i == destination:
					ans += 1
				elif i != destination:
					q.append(i)
		return ans


class Solution:

	def countPaths(self, V, adj, source, destination):
		q = [source]
		count = 0
		while q:
			top = q.pop(0)
			for i in adj[top]:
				if i == destination:
					count += 1
				else:
					q.append(i)
		return count

	def countPaths(self, V, adj, source, destination):
		if source == destination:
			return 1
		(q, pos, len1, count) = ([source], 0, 1, 0)
		while pos < len1:
			top = q.pop(0)
			for i in adj[top]:
				if i == destination:
					count += 1
				else:
					q.append(i)
					len1 += 1
			pos += 1
		return count


from collections import deque

class Solution:

	def countPaths(self, V, adj, source, destination):
		ans = []
		q = deque([(source, [source])])
		while q:
			(node, path) = q.popleft()
			if node == destination:
				ans.append(path)
			else:
				for adjnode in adj[node]:
					q.append((adjnode, path + [adjnode]))
		return len(ans)


class Solution:

	def countPaths(self, V, adj, source, destination):
		pathCount = [0]
		self.countPathsUtil(V, adj, source, destination, pathCount)
		return pathCount[0]

	def countPathsUtil(self, V, adj, source, destination, pathCount):
		if source == destination:
			pathCount[0] += 1
			return
		for v in adj[source]:
			self.countPathsUtil(V, adj, v, destination, pathCount)


class Solution:

	def countPaths(self, V, adj, source, destination):
		vis = [0] * V

		def rec(nod, destination):
			if nod == destination:
				return 1
			ans = 0
			for i in adj[nod]:
				ans += rec(i, destination)
			return ans
		op = rec(source, destination)
		return op


class Solution:

	def dfs(self, u, adj, dest):
		if u == dest:
			return 1
		count = 0
		for v in adj[u]:
			count += self.dfs(v, adj, dest)
		return count

	def countPaths(self, V, adj, source, destination):
		return self.dfs(source, adj, destination)


class Solution:

	def countPaths(self, V, adj, source, destination):
		count = 0
		if source == destination:
			return 1
		for neigh in adj[source]:
			count += self.countPaths(V, adj, neigh, destination)
		return count


class Solution:

	def __init__(self):
		self.count = 0
		self.visited = []

	def dfs(self, c, V, adj, d):
		if c == d:
			self.count += 1
			return
		self.visited[c] = 0
		for nei in adj[c]:
			if self.visited[nei] == -1 or self.visited[nei] == 1:
				self.dfs(nei, V, adj, d)
		self.visited[c] = 1

	def countPaths(self, V, adj, source, destination):
		self.visited = [-1] * V
		self.dfs(source, V, adj, destination)
		return self.count


class Solution:

	def countPaths(self, V, adj, source, destination):
		self.count = 0
		self.visited = [False] * V

		def dfs(ele, visited):
			visited[ele] = True
			if ele == destination:
				self.count += 1
			for i in adj[ele]:
				if not visited[i]:
					dfs(i, visited)
				visited[i] = False
		dfs(source, self.visited)
		return self.count


class Solution:

	def countPaths(self, V, adj, source, destination):
		if source == destination:
			return 1
		count = 0
		queue = [source]
		while queue:
			node = queue.pop(0)
			if node == destination:
				count += 1
				continue
			for it in adj[node]:
				queue.append(it)
		return count


class Solution:

	def df(self, s, d, adj, v, count):
		v[s] = 1
		if s == d:
			count[0] = count[0] + 1
		else:
			for i in adj[s]:
				if v[i] == 0:
					self.df(i, d, adj, v, count)
		v[s] = 0

	def countPaths(self, V, adj, source, destination):
		v = [0] * V
		count = [0]
		self.df(source, destination, adj, v, count)
		return count[0]


class Solution:

	def df(self, s, d, adj, v, count):
		v[s] = 1
		if s == d:
			count[0] = count[0] + 1
		else:
			i = 0
			while i < len(adj[s]):
				if not v[adj[s][i]]:
					self.df(adj[s][i], d, adj, v, count)
				i = i + 1
		v[s] = 0

	def countPaths(self, V, adj, source, destination):
		v = [0] * V
		count = [0]
		self.df(source, destination, adj, v, count)
		return count[0]


class Solution:

	def countPaths(self, V, adj, source, destination):
		self.result = 0
		if source == destination:
			self.result += 1

		def dfs(index, target, adj):
			for val in adj[index]:
				if val == target:
					self.result += 1
				else:
					dfs(val, target, adj)
		dfs(source, destination, adj)
		return self.result


class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = set()
		self.ans = 0

		def dfs(node):
			if node == destination:
				self.ans += 1
			visited.add(node)
			for v in adj[node]:
				if v not in visited:
					dfs(v)
			visited.remove(node)
		dfs(source)
		return self.ans


class Solution:

	def dfsHelper(self, adj, source, destination, recStack):
		recStack.add(source)
		result = 0
		for neighbor in adj[source]:
			if not neighbor in recStack:
				if neighbor == destination:
					result += 1
				else:
					result += self.dfsHelper(adj, neighbor, destination, recStack)
		recStack.discard(source)
		return result

	def countPaths(self, V, adj, source, destination):
		recStack = set()
		if source == destination:
			return 1
		return self.dfsHelper(adj, source, destination, recStack)


class Solution:

	def __init__(self):
		self.count = 0

	def countPaths(self, V, adj, source, destination):
		isVisited = [False for i in range(V)]
		self.dfs(V, adj, source, destination, isVisited)
		return self.count

	def dfs(self, V, adj, target, destination, isVisited):
		if target == destination:
			self.count += 1
			return None
		isVisited[target] = True
		for nbr in adj[target]:
			if not isVisited[nbr]:
				self.dfs(V, adj, nbr, destination, isVisited)
		isVisited[target] = False
		return None


class Solution:

	def countPaths(self, V, adj, source, destination):
		count = 0
		s = source
		d = destination

		def dfs(x, s, d):
			if x == d:
				return 1
			summ = 0
			for node in adj[x]:
				summ += dfs(node, s, d)
			return summ
		return dfs(s, s, d)


class Solution:

	def countPaths(self, V, adj, source, destination):
		paths = [0]

		def dfs(curr):
			if curr == destination:
				paths[0] += 1
				return
			for nxt in adj[curr]:
				dfs(nxt)
		dfs(source)
		return paths[0]


class Solution:

	def find(self, s, d, adj, V, dp):
		if s == d:
			return 1
		if dp[s] != -1:
			return dp[s]
		a = 0
		for x in adj[s]:
			a += self.find(x, d, adj, V, dp)
		dp[s] = a
		return a

	def countPaths(self, V, adj, source, destination):
		dp = [-1] * V
		return self.find(source, destination, adj, V, dp)


class Solution:

	def countPaths(self, V, adj, source, destination):

		def dfs(i):
			if i == destination:
				return 1
			j = 0
			for k in adj[i]:
				j += dfs(k)
			return j
		return dfs(source)


class Solution:

	def countPaths(self, V, adj, source, destination):
		global all_paths, visited
		graph = adj
		all_paths = []
		n = V
		visited = [False] * n

		def dfs(v, path, n, visited):
			global all_paths
			path.append(v)
			back = path.copy()
			visited[v] = True
			if v == n:
				all_paths.append(path)
				visited[v] = True
				return
			for i in graph[v]:
				if not visited[i]:
					dfs(i, path, n, visited)
					path = back.copy()
					visited[i] = False
		dfs(source, [], destination, visited)
		return len(all_paths)


class Solution:

	def countPaths(self, V, adj, source, destination):

		def find_paths(node):
			if node == destination:
				return 1
			total = 0
			for n in adj[node]:
				total += find_paths(n)
			return total
		return find_paths(source)


class Solution:

	def countPathstil(self, adj, s, d, visit, res):
		visit[s] = True
		if s == d:
			res[0] += 1
		else:
			i = 0
			while i < len(adj[s]):
				if not visit[adj[s][i]]:
					self.countPathstil(adj, adj[s][i], d, visit, res)
				i += 1
		visit[s] = False

	def countPaths(self, V, adj, source, destination):
		visited = [False] * V
		pathcount = [0]
		self.countPathstil(adj, source, destination, visited, pathcount)
		return pathcount[0]


class Solution:

	def countPaths(self, V, adj, source, destination):
		self.paths = 0
		visited = [False] * V
		visited[source] = True

		def findpaths(v, d):
			visited[v] = True
			if v == d:
				self.paths += 1
			else:
				for neig in adj[v]:
					if visited[neig] == False:
						findpaths(neig, d)
			visited[v] = False
		findpaths(source, destination)
		return self.paths


class Solution:

	def countPaths(self, V, adj, source, destination):

		def dfs(node, count, visited):
			visited[node] = True
			if node == destination:
				count[0] += 1
			else:
				for i in adj[node]:
					if visited[i] == False:
						dfs(i, count, visited)
			visited[node] = False
		visited = [False] * len(adj)
		count = [0]
		dfs(source, count, visited)
		return count[0]


class Solution:

	def countPaths(self, V, adj, source, destination):
		ans = 0
		if source == destination:
			return 1
		for u in adj[source]:
			ans += self.countPaths(V, adj, u, destination)
		return ans


class Solution:

	def dfs(self, u, vis, adj, st):
		vis[u] = True
		for v in adj[u]:
			if not vis[v]:
				self.dfs(v, vis, adj, st)
		st.append(u)

	def countPaths(self, V, adj, source, destination):
		st = []
		vis = [False] * V
		for i in range(V):
			if not vis[i]:
				self.dfs(i, vis, adj, st)
		ans = [0] * V
		ans[source] = 1
		while st:
			u = st.pop()
			for v in adj[u]:
				ans[v] += ans[u]
		return ans[destination]


class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = [False] * V
		count = 0
		count = self.solve(V, adj, source, destination, visited, count)
		return count

	def solve(self, V, adj, s, d, visited, c):
		visited[s] = True
		if s == d:
			c += 1
		else:
			for i in adj[s]:
				c = self.solve(V, adj, i, d, visited, c)
		return c


class Solution:

	def countPaths(self, V, adj, source, destination):
		q = [source]
		c = 0
		while q:
			x = q.pop(0)
			for i in adj[x]:
				q.append(i)
			if x == destination:
				c = c + 1
		return c


class Solution:
	visited = None
	count = 0

	def logic(self, V, adj, source, destination):
		self.visited[source] = True
		if source == destination:
			self.count += 1
		else:
			for i in adj[source]:
				if not self.visited[i]:
					self.logic(V, adj, i, destination)
		self.visited[source] = False

	def countPaths(self, V, adj, source, destination):
		self.visited = [False for _ in range(V)]
		self.logic(V, adj, source, destination)
		return self.count


class Solution:

	def countPaths(self, V, adj, source, destination):
		visit = [False for i in range(V)]
		count = [0]
		self.rec(visit, source, destination, count, source)
		return count[0]

	def rec(self, visit, source, dest, count, n):
		if n == dest:
			count[0] += 1
			return
		visit[n] = True
		for i in adj[n]:
			if visit[i] == False:
				self.rec(visit, source, dest, count, i)
		visit[n] = False


class Solution:

	def countPaths(self, V, adj, source, destination):
		visited = [False] * V
		self.res = 0

		def dfs(s, d, visited):
			visited[s] = True
			if s == d:
				self.res += 1
			for u in adj[s]:
				if not visited[u]:
					dfs(u, d, visited)
			visited[s] = False
		dfs(source, destination, visited)
		return self.res


class Solution:

	def countPaths(self, V, adj, src, dest):
		visited = [False] * V
		count = [0]
		self.DFS(adj, src, visited, dest, count)
		return count[0]

	def DFS(self, adj, u, visited, dest, count):
		if u == dest:
			count[0] += 1
			return
		visited[u] = True
		for v in adj[u]:
			if not visited[v]:
				self.DFS(adj, v, visited, dest, count)
		visited[u] = False


class Solution:

	def countPaths(self, V, adj, source, destination):
		cnt = 0

		def dfs(root, dest):
			nonlocal cnt
			if root == dest:
				cnt += 1
			for node in adj[root]:
				dfs(node, dest)
		dfs(source, destination)
		return cnt


class Solution:

	def countPaths(self, V, adj, source, destination):
		memo = [None] * V

		def dfs(v):
			if v == destination:
				return 1
			if memo[v] != None:
				return memo[v]
			memo[v] = 0
			for nei in adj[v]:
				memo[v] += dfs(nei)
			return memo[v]
		return dfs(source)


from collections import defaultdict

class Solution:

	def countPaths(self, V, adj, s, d):
		ans = [0]

		def DFS(node):
			vis[node] = 1
			if node == d:
				ans[0] += 1
				vis[node] = 0
				return
			for x in adj[node]:
				if not vis[x]:
					DFS(x)
			vis[node] = 0
		vis = [0] * V
		DFS(s)
		return ans[0]