Given an undirected graph with V vertices(numbered from 1 to V) and E edges. Find the number of good components in the graph.
A component of the graph is good if and only if the component is a fully connected component.
Note: A fully connected component is a subgraph of a given graph such that there's an edge between every pair of vertices in a component, the given graph can be a disconnected graph. Consider the adjacency list from vertices 1.
Example 1:
Input: 
E=3 V=3
adj:
{{1, 2},
 {1, 3},
 {3, 2}}
Output: 1
Explanation: We can see that there is only one 
component in the graph and in this component 
there is a edge between any two vertces.
Example 2:
Input:
E=5 V=7
adj:
{{1, 2},
 {7, 2},
 {3, 5},
 {3, 4},
 {4, 5}}
Output: 2
Explanation: We can see that there are 3 components
in the graph. For 1-2-7 there is no edge between
1 to 7, so it is not a fully connected component.
Rest 2 are individually fully connected component.
Your Task:
You don't need to read input or print anything. Your task is to complete the function
findNumberOfGoodComponent() which takes an integer V and a list of edges adj as input parameters and returns an integer denoting the number of good components. 
Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(depth of the graph)
Constraints:
1 ≤ V, E ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Starter code: #User function Template for python3



import collections

from collections import deque

from collections import defaultdict



class Solution:

    def findNumberOfGoodComponent(self, V, adj):

        # code here

Solutions:
import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = [0 for i in range(V + 1)]
		ans = 0
		for i in range(1, V + 1):
			count = [0]
			su = [0]
			if visited[i] == 0:
				self.dfs(i, visited, adj, count, su)
				if su[0] // 2 == count[0] * (count[0] - 1) // 2 or su[0] == 0:
					ans += 1
		return ans

	def dfs(self, node, visited, adj, count, su):
		visited[node] = 1
		for neigh in adj[node]:
			if visited[neigh] == 0:
				self.dfs(neigh, visited, adj, count, su)
		su[0] += len(adj[node])
		count[0] += 1


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, graph):
		visited = [False for i in range(V + 1)]
		count = 0

		def dfs(sv):
			visited[sv] = True
			nonlocal v
			nonlocal e
			v += 1
			e += len(graph[sv])
			for des in graph[sv]:
				if visited[des] == False:
					dfs(des)
		for i in range(1, V + 1):
			if visited[i] == False:
				e = 0
				v = 0
				dfs(i)
				temp = v * (v - 1) // 2
				if temp == e // 2:
					count += 1
		return count


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def solve(node, isVisited):
			if node in isVisited:
				return (0, 0)
			isVisited.add(node)
			res = 0
			totalnode = 1
			for child in adj[node]:
				(val, data) = solve(child, isVisited)
				res = 1 + val + res
				totalnode += data
			return (res, totalnode)
		res = 0
		isVisited = set()
		for i in range(1, V + 1):
			if i not in isVisited:
				val = solve(i, isVisited)
				if val[1] * (val[1] - 1) == val[0]:
					res += 1
		return res


import collections
from collections import deque
from collections import Counter

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = set()
		edge_counts = Counter()
		q = deque()
		good_count = 0
		for i in range(1, V + 1):
			if i in visited:
				continue
			edge_counts.clear()
			q.append(i)
			while q:
				v = q.pop()
				if v in visited:
					continue
				visited.add(v)
				for u in adj[v]:
					q.append(u)
					edge_counts[v] += 1
					edge_counts[u] += 1
			n = 2 * (len(edge_counts) - 1)
			if all((ec == n for ec in edge_counts.values())):
				good_count += 1
		return good_count


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, edges):

		def dfs(s, visit):
			ans = [s]
			visit.add(s)
			for ele in adj[s]:
				if ele not in visit:
					s = dfs(ele, visit)
					for i in s:
						ans.append(i)
			return ans
		res = 0
		visit = set()
		for i in range(1, len(adj)):
			if i not in visit:
				ans = dfs(i, visit)
				for x in ans:
					if len(adj[x]) != len(ans) - 1:
						break
				else:
					res += 1
		return res


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		connected = 0
		seen = [False for _ in range(V + 1)]

		def dfs(node):
			seen[node] = True
			self.edges += len(adj[node])
			for neighbor in adj[node]:
				if not seen[neighbor]:
					self.vertices += 1
					dfs(neighbor)
		for i in range(1, V + 1):
			if not seen[i]:
				self.edges = 0
				self.vertices = 1
				dfs(i)
				if self.vertices * (self.vertices - 1) / 2 == self.edges / 2:
					connected += 1
		return connected


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, graph, visited, u):
		res = [u]
		visited[u] = True
		for v in graph[u]:
			if not visited[v]:
				res.extend(self.dfs(graph, visited, v))
		return res

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False] * (V + 1)
		res = 0
		for u in range(1, V + 1):
			if not visited[u]:
				nodes = self.dfs(adj, visited, u)
				if all((len(adj[node]) == len(nodes) - 1 for node in nodes)):
					res += 1
		return res


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = [0 for i in range(V + 1)]
		c = 0
		for i in range(1, V + 1):
			if visited[i] == 0:
				dic = {}
				c += 1
				self.dfs(i, adj, visited, dic)
				n = len(dic)
				for ele in dic:
					if dic[ele] < n - 1:
						c -= 1
						break
		return c

	def dfs(self, node, adj, visited, dic):
		dic[node] = 0
		visited[node] = 1
		for ele in adj[node]:
			dic[node] += 1
			if visited[ele] == 0:
				self.dfs(ele, adj, visited, dic)
		return


class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def solve(node, isVisited):
			if node in isVisited:
				return (0, 0)
			isVisited.add(node)
			res = 0
			totalnode = 1
			for child in adj[node]:
				(val, data) = solve(child, isVisited)
				res = 1 + val + res
				totalnode += data
			return (res, totalnode)
		res = 0
		isVisited = set()
		for i in range(1, V + 1):
			if i not in isVisited:
				val = solve(i, isVisited)
				if val[1] * (val[1] - 1) == val[0]:
					res += 1
		return res


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		timer = [-1 for _ in range(V + 1)]
		goodC = 0

		def DFS_count(root, parent, tm, tempV, tempE):
			timer[root] = tm
			for v in adj[root]:
				if timer[v] == -1:
					(tempV, tempE) = DFS_count(v, root, tm + 1, tempV + 1, tempE + 1)
				elif v != parent and timer[v] < tm:
					tempE = tempE + 1
			return (tempV, tempE)
		for u in range(1, V + 1):
			if timer[u] == -1:
				(countVk, countEk) = DFS_count(u, None, 0, 1, 0)
				if countVk * (countVk - 1) // 2 == countEk:
					goodC = goodC + 1
		return goodC


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def dfs(u):
			visited[u] = True
			curr.append(u)
			for v in adj[u]:
				if not visited[v]:
					dfs(v)
		visited = [False] * (V + 1)
		curr = []
		cnt = 0
		for u in range(1, V + 1):
			if not visited[u]:
				curr.clear()
				dfs(u)
				size = len(curr)
				isFully = True
				for n in curr:
					if len(adj[n]) != size - 1:
						isFully = False
						break
				if isFully:
					cnt += 1
		return cnt


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = set()

		def dfs(n, ns, edges):
			nonlocal visited
			ns.add(n)
			visited.add(n)
			for nbr in adj[n]:
				edges.add((min(n, nbr), max(n, nbr)))
				if nbr not in ns:
					dfs(nbr, ns, edges)
		ans = 0
		for n in range(1, V + 1):
			if n not in visited:
				ns = set()
				edges = set()
				dfs(n, ns, edges)
				nv = len(ns)
				ne = len(edges)
				if nv * (nv - 1) // 2 == ne:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		nodes = []
		visited = set()

		def dfs(node):
			area = 1
			visited.add(node)
			nodes.append(node)
			for nextV in adj[node]:
				if nextV in visited:
					continue
				area += dfs(nextV)
			return area
		cnt = 0
		for i in range(1, V + 1):
			if i in visited:
				continue
			while nodes:
				nodes.pop()
			num = dfs(i)
			isGood = True
			for v in nodes:
				isGood = isGood and len(adj[v]) == num - 1
			if isGood:
				cnt += 1
		return cnt


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def util(node, iv):
			if node in iv:
				return (0, 0)
			iv.add(node)
			res = 0
			total = 1
			for ch in adj[node]:
				(val, data) = util(ch, iv)
				res = 1 + val + res
				total += data
			return (res, total)
		res = 0
		iv = set()
		for i in range(1, V + 1):
			if i not in iv:
				val = util(i, iv)
				if val[1] * (val[1] - 1) == val[0]:
					res += 1
		return res


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, u, comp, seen, graph):
		seen.add(u)
		comp.add(u)
		for v in graph[u]:
			if v in seen:
				continue
			self.dfs(v, comp, seen, graph)

	def findNumberOfGoodComponent(self, V, graph):
		ans = 0
		seen = set()
		for u in range(1, V + 1):
			if u in seen:
				continue
			comp = set()
			self.dfs(u, comp, seen, graph)
			if all((len(graph[x]) == len(comp) - 1 for x in comp)):
				ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict
(vertices, edges) = (0, 0)
global vis
vis = set()

def dfs(adj, v):
	vis.add(v)
	global vertices, edges
	edges += len(adj[v])
	for i in adj[v]:
		if i not in vis:
			vertices += 1
			dfs(adj, i)
	return

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		ans = 0
		global vertices, edges
		(vertices, edges) = (0, 0)
		vis.clear()
		for i in range(1, V + 1):
			if i not in vis:
				edges = 0
				vertices = 1
				dfs(adj, i)
				if vertices * (vertices - 1) / 2 == edges / 2:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, n, adj):
		g = adj

		def helper(node, par, arr):
			vis[node] = 1
			arr.append(node)
			for child in g[node]:
				if child == par or vis[child]:
					continue
				helper(child, node, arr)
			return arr
		vis = defaultdict(int)
		ans = 0
		for i in range(1, n + 1):
			if not vis[i]:
				lis = helper(i, -1, [])
				flag = 0
				for i in lis:
					if len(g[i]) != len(lis) - 1:
						flag = 1
						break
				if flag == 0:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def dfs(v, adj, vis, ele):
			vis[v] = True
			ele.append(v)
			for i in adj[v + 1]:
				if not vis[i - 1]:
					dfs(i - 1, adj, vis, ele)
		ans = 0
		vis = [False for i in range(V)]
		for i in range(V):
			if not vis[i]:
				ele = []
				dfs(i, adj, vis, ele)
				flag = False
				for i in ele:
					if len(adj[i + 1]) < len(ele) - 1:
						flag = True
						break
				if not flag:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		res = 0
		vis = [False] * (V + 1)

		def dfs(i):
			vis[i] = True
			dfs.nodes += 1
			for k in adj[i]:
				mn = i
				mx = k
				if mn > mx:
					(mn, mx) = (mx, mn)
				dfs.edges.add(str(mn) + '*' + str(mx))
				if not vis[k]:
					dfs(k)
		nC2 = lambda n: n * (n - 1) // 2
		dfs.edges = set()
		for i in range(1, V + 1):
			if vis[i]:
				continue
			dfs.nodes = 0
			dfs(i)
			if len(dfs.edges) == nC2(dfs.nodes):
				res += 1
			dfs.edges.clear()
		return res


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		vis = [False] * V
		ans = 0
		for i in adj:
			for j in range(0, len(i)):
				i[j] -= 1
		adj.pop(0)
		for i in range(0, V):
			if not vis[i]:
				l = [0, 0]
				self.dfs(i, adj, l, vis)
				ans += l[0] * (l[0] - 1) == l[1]
		return ans

	def dfs(self, node, adj, l, vis):
		vis[node] = True
		l[0] += 1
		l[1] += len(adj[node])
		for i in adj[node]:
			if vis[i]:
				continue
			self.dfs(i, adj, l, vis)


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, v, adj, visited):
		visited[v] = 1
		self.vertices += 1
		self.edges += len(adj[v])
		for to in adj[v]:
			if not visited[to]:
				self.dfs(to, adj, visited)

	def findNumberOfGoodComponent(self, V, adj):
		ans = 0
		visited = [0] * (V + 1)
		for i in range(1, V + 1):
			if not visited[i]:
				self.vertices = 0
				self.edges = 0
				self.dfs(i, adj, visited)
				self.edges //= 2
				if self.edges == self.vertices * (self.vertices - 1) // 2:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, adj, visited, ele):
		total = [ele]
		visited[ele] = True
		for nei in adj[ele]:
			if not visited[nei]:
				total.extend(self.dfs(adj, visited, nei))
		return total

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False] * (V + 1)
		res = 0
		for ele in range(1, V + 1):
			if not visited[ele]:
				nodes = self.dfs(adj, visited, ele)
				if all((len(adj[node]) == len(nodes) - 1 for node in nodes)):
					res += 1
		return res


import collections
from collections import deque
from collections import defaultdict

def fun(i, visit, adj):
	visit[i] = 1
	q = deque()
	t = 0
	q.append(i)
	while q:
		t += 1
		u = q.popleft()
		for j in adj[u]:
			if visit[j] == 0:
				q.append(j)
				visit[j] = 1
	return t

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visit = [0] * (V + 1)
		c = 0
		for i in range(1, V + 1):
			if visit[i] == 0:
				p = False
				a = fun(i, visit, adj)
				if a - 1 == len(adj[i]):
					for j in adj[i]:
						if a - 1 != len(adj[j]):
							p = True
					if p == False:
						c += 1
		return c


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def getCompNum(self, node, comp, vis, adj):
		vis[node] = 1
		comp[0] += 1
		comp[1] = max(comp[1], len(adj[node]))
		comp[2] = min(comp[2], len(adj[node]))
		for adjN in adj[node]:
			if vis[adjN] == 0:
				self.getCompNum(adjN, comp, vis, adj)
		return 1

	def findNumberOfGoodComponent(self, V, adj):
		v = V
		vis = [0 for i in range(v + 1)]
		ans = 0
		for i in range(1, v + 1):
			if vis[i] == 0:
				comp = [0, len(adj[i]), len(adj[i])]
				self.getCompNum(i, comp, vis, adj)
				if comp[1] == comp[2] and comp[0] - 1 == comp[1]:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def solve(node, isVisited):
			if node in isVisited:
				return (0, 0)
			isVisited.add(node)
			ans = 0
			tn = 1
			for child in adj[node]:
				(v, d) = solve(child, isVisited)
				ans = 1 + v + ans
				tn += d
			return (ans, tn)
		ans = 0
		isVisited = set()
		for a in range(1, V + 1):
			if a not in isVisited:
				v = solve(a, isVisited)
				if v[1] * (v[1] - 1) == v[0]:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, i, visited, adj):
		visited[i] = True
		self.edge += len(adj[i])
		self.vertices += 1
		for j in adj[i]:
			if visited[j] == False:
				self.dfs(j, visited, adj)

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False] * (V + 1)
		count = 0
		for i in range(1, V + 1):
			if visited[i] != True:
				self.edge = 0
				self.vertices = 0
				self.dfs(i, visited, adj)
				self.edge = self.edge // 2
				if self.edge == self.vertices * (self.vertices - 1) // 2:
					count += 1
		return count


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		count = 0
		visited = set()
		len_visited = 0
		for v in range(1, V + 1):
			if v in visited:
				continue
			if adj[v] != 0:
				edges = 0
				que = []
				que.append(v)
				while que:
					ver = que.pop(0)
					visited.add(ver)
					edges += len(adj[ver])
					for i in adj[ver]:
						if i not in visited:
							que.append(i)
						visited.add(i)
			no_of_vertices = len(visited) - len_visited
			if no_of_vertices * (no_of_vertices - 1) == edges:
				count += 1
			len_visited = len(visited)
		return count


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False] * (V + 1)

		def bfs(u):
			visited[u] = True
			queue = deque([])
			con = 0
			for v in adj[u]:
				queue.append(v)
				visited[v] = True
				con += 1
			good = 1
			while queue:
				u = queue.popleft()
				if len(adj[u]) != con:
					good = 0
				for v in adj[u]:
					if visited[v] == False:
						queue.append(v)
						visited[v] = True
						good = 0
			return good
		goodComponents = 0
		for u in range(1, V + 1):
			if visited[u] == False:
				goodComponents += bfs(u)
		return goodComponents


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, graph, node):
		self.visited[node] = True
		self.v_count = self.v_count + 1
		self.e_count = self.e_count + len(graph[node])
		for currnode in graph[node]:
			if not self.visited[currnode]:
				self.dfs(graph, currnode)

	def findNumberOfGoodComponent(self, V, adj):
		comp = 0
		self.visited = [False] * (V + 1)
		for i in range(1, V + 1):
			if not self.visited[i]:
				self.v_count = 0
				self.e_count = 0
				self.dfs(adj, i)
				expec_edge = self.v_count * (self.v_count - 1)
				if expec_edge == self.e_count:
					comp = comp + 1
		return comp


import collections
from collections import deque
from collections import defaultdict

def dfs(adj, visited, i):
	visited[i] = True
	queue = deque([i])
	temp = 0
	while queue:
		temp += 1
		x = queue.popleft()
		for j in adj[x]:
			if not visited[j]:
				queue.append(j)
				visited[j] = True
	return temp

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False for i in range(V + 1)]
		ans = 0
		for i in range(1, V + 1):
			if not visited[i]:
				flag = False
				res = dfs(adj, visited, i)
				if res - 1 == len(adj[i]):
					for j in adj[i]:
						if res - 1 != len(adj[j]):
							flag = True
					if flag == False:
						ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

def dfs(adj, i, visited):
	visited[i] = True
	queue = deque([i])
	t = 0
	while queue:
		u = queue.popleft()
		t += 1
		for j in adj[u]:
			if visited[j] == False:
				queue.append(j)
				visited[j] = True
	return t
	e_count += len(adj[i])
	for j in adj[i]:
		if visited[j] == False:
			dfs(adj, j, visited, e_count, v_count)

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		visited = [False for _ in range(V + 1)]
		ans = 0
		for i in range(1, V + 1):
			if visited[i] == False:
				flag = False
				temp = dfs(adj, i, visited)
				if temp - 1 == len(adj[i]):
					for j in adj[i]:
						if temp - 1 != len(adj[j]):
							flag = True
					if flag == False:
						ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):

		def DFS(curr, size, adjli, visited):
			nonlocal flag, total
			visited[curr] = True
			total += 1
			if size != len(adjli[curr]):
				flag = False
			for new_curr in adjli[curr]:
				if not visited[new_curr]:
					DFS(new_curr, size, adjli, visited)
			return
		ans = 0
		visited = [False] * (V + 1)
		for node in range(1, V + 1):
			if not visited[node]:
				total = 0
				flag = True
				DFS(node, len(adj[node]), adj, visited)
				if flag and total - 1 == len(adj[node]):
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

def dfs(node, adj, vis, val):
	for v in adj[node]:
		val[1] += 1
		if not vis[v]:
			vis[v] = True
			val[0] += 1
			dfs(v, adj, vis, val)

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		vis = [False] * (V + 1)
		ans = 0
		for v in range(1, V + 1):
			if not vis[v]:
				val = [1, 0]
				vis[v] = True
				dfs(v, adj, vis, val)
				n = val[0]
				edg = n * (n - 1) // 2
				if edg == val[1] // 2:
					ans += 1
		return ans


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def __init__(self):
		self.vertices = 0
		self.edges = 0

	def dfs(self, node, vis, adj):
		vis[node] = True
		self.edges += len(adj[node])
		for i in adj[node]:
			if vis[i] == False:
				self.vertices += 1
				self.dfs(i, vis, adj)

	def findNumberOfGoodComponent(self, V, adj):
		vis = [False] * (V + 1)
		full = 0
		for i in range(1, V + 1):
			if vis[i] == False:
				self.edges = 0
				self.vertices = 1
				self.dfs(i, vis, adj)
				if self.vertices * (self.vertices - 1) == self.edges:
					full += 1
		return full


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def findNumberOfGoodComponent(self, V, adj):
		count = 0
		visited = set()
		len_visited = 0

		def helper(v):
			if v in visited:
				return 0
			visited.add(v)
			if len(adj[v]) == 0:
				return 0
			edges = 0
			for ver in adj[v]:
				edges += helper(ver)
				edges += 1
			return edges
		for v in range(1, V + 1):
			if v in visited:
				continue
			edges = helper(v)
			no_of_vertices = len(visited) - len_visited
			if no_of_vertices * (no_of_vertices - 1) == edges:
				count += 1
			len_visited = len(visited)
		return count


import collections
from collections import deque
from collections import defaultdict

class Solution:

	def dfs(self, adj, i, a, k):
		k.append(i)
		a[i] += 1
		for j in adj[i]:
			if not a[j]:
				self.dfs(adj, j, a, k)

	def findNumberOfGoodComponent(self, V, adj):
		a = [0] * (V + 1)
		ans = 0
		for i in range(1, V + 1):
			if not a[i]:
				k = []
				self.dfs(adj, i, a, k)
				f = False
				for i in k:
					if len(adj[i]) < len(k) - 1:
						f = True
						break
				if not f:
					ans += 1
		return ans