Given N nodes of a tree and a list of edges. Find the minimum number of nodes to be selected to light up all the edges of the tree.
An edge lights up when at least one node at the end of the edge is selected.
Example 1:
Input:
N = 6
edges[] = {(1,2), (1,3), (2,4), (3,5), (3,6)}
Output: 2
Explanation: Selecting nodes 2 and 3 lights
up all the edges.
Example 2:
Input:
N = 3
arr[] = {(1,2), (1,3)}
Output: 1
Explanation: Selecting Node 1 
lights up all the edges.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function countVertex() which takes the number of nodes N, and the list of edges as input parameters and returns the minimum number of nodes selected.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ edges ≤ N
Given graph is a valid tree.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: Tree algorithms

Dynamic programming

Data structures

Graph traversal

Starter code: #User function Template for python3



class Solution:

    def countVertex(self, N, edges):

        #code here

Solutions:
class Solution:

	def dfs(self, graph, u, p):
		(exc, inc) = (0, 1)
		for v in graph[u]:
			if v != p:
				(cexc, cinc) = self.dfs(graph, v, u)
				exc += cinc
				inc += min(cinc, cexc)
		return (exc, inc)

	def countVertex(self, N, edges):
		graph = [[] for _ in range(N)]
		for (u, v) in edges:
			graph[u - 1].append(v - 1)
			graph[v - 1].append(u - 1)
		return min(self.dfs(graph, 0, -1))


class Solution:

	def dfs(self, adj, src, par, val):
		for v in adj[src]:
			if v != par:
				self.dfs(adj, v, src, val)
		for v in adj[src]:
			if v != par:
				val[src][0] += val[v][1]
				val[src][1] += min(val[v][1], val[v][0])

	def countVertex(self, N, edges):
		adj = [[] for i in range(N + 1)]
		for i in range(N - 1):
			adj[edges[i][0]].append(edges[i][1])
			adj[edges[i][1]].append(edges[i][0])
		val = [[] for i in range(N + 1)]
		for i in range(1, N + 1):
			val[i] = [0, 1]
		self.dfs(adj, 1, 1, val)
		return min(val[1][0], val[1][1])


class Solution:

	def __init__(self):
		self.graph = {}

	def DFS(self, node, parent):
		l = 1
		nl = 0
		if node in self.graph:
			for child in self.graph[node]:
				if child == parent:
					continue
				[cl, cnl] = self.DFS(child, node)
				l += min(cl, cnl)
				nl += cl
		return [l, nl]

	def countVertex(self, n, edges):
		for edge in edges:
			u = edge[0]
			v = edge[1]
			if u not in self.graph:
				self.graph[u] = []
			if v not in self.graph:
				self.graph[v] = []
			self.graph[u].append(v)
			self.graph[v].append(u)
		[l, nl] = self.DFS(1, -1)
		return min(l, nl)


class Solution:

	def countVertex(self, N, edges):
		adj = [[] for i in range(N + 1)]
		vis = [False] * (N + 1)
		for (u, v) in edges:
			adj[u].append(v)
			adj[v].append(u)

		def dfs(node):
			vis[node] = True
			isSelected = False
			for nb in adj[node]:
				if not vis[nb] and (not dfs(nb)):
					isSelected = True
			if isSelected:
				count[0] += 1
			return isSelected
		count = [0]
		dfs(1)
		return count[0]


class Solution:

	def __init__(self):
		self.count = 0

	def searchNode(self, curr, adj, visit):
		currSelected = False
		for child in adj[curr]:
			if visit[child] == False:
				visit[child] = True
				isChildSelected = self.searchNode(child, adj, visit)
				if isChildSelected == False:
					currSelected = True
		if currSelected == True:
			self.count += 1
		return currSelected

	def countVertex(self, N, edges):
		adj = [[] for _ in range(N + 2)]
		for edge in edges:
			u = edge[0]
			v = edge[1]
			adj[u].append(v)
			adj[v].append(u)
		visit = [False] * (N + 2)
		visit[1] = True
		self.searchNode(1, adj, visit)
		return self.count


class Solution:

	def countVertex(self, n, edges):

		def dfs(u):
			visit[u] = True
			select = False
			for v in adj[u]:
				if visit[v] == False and (not dfs(v)):
					select = True
			if select == True:
				cnt[0] += 1
			return select
		adj = [[] for i in range(n + 1)]
		for edge in edges:
			(u, v) = edge
			adj[u].append(v)
			adj[v].append(u)
		cnt = [0]
		visit = [False] * (n + 1)
		dfs(1)
		return cnt[0]


from collections import defaultdict

class Solution:

	def countVertex(self, N, edges):
		dp = [[-1 for i in range(2)] for j in range(N + 1)]

		def rec(i, l, par):
			vis.add(i)
			if dp[i][l] != -1:
				return dp[i][l]
			if not d[i]:
				return 0
			ans = 0
			for j in d[i]:
				if j == par:
					continue
				if l == 1:
					keep = 1 + rec(j, 1, i)
					no_keep = rec(j, 0, i)
					ans += min(keep, no_keep)
				elif l == 0:
					keep = 1 + rec(j, 1, i)
					no_keep = float('inf')
					ans += min(keep, no_keep)
			dp[i][l] = ans
			return ans
		d = defaultdict(list)
		for (i, j) in edges:
			d[i].append(j)
			d[j].append(i)
		vis = set()
		return min(1 + rec(1, 1, -1), rec(1, 0, -1))


class Solution:

	def find_children(self, node, adj, vis, s0, s1):
		vis[node] = 1
		s1[node] = 1
		for x in adj[node]:
			if not vis[x]:
				self.find_children(x, adj, vis, s0, s1)
				s1[node] += min(s0[x], s1[x])
				s0[node] += s1[x]

	def visit(self, node, s0, s1, adj_tree):
		s1[node] = 1
		for x in adj_tree[node]:
			self.visit(x, s0, s1, adj_tree)
			s1[node] += min(s0[x], s1[x])
			s0[node] += s1[x]
		return

	def countVertex(self, N, edges):
		adj = [[] for i in range(N)]
		for (a, b) in edges:
			adj[a - 1].append(b - 1)
			adj[b - 1].append(a - 1)
		vis = [0] * N
		root = 0
		s0 = [0] * N
		s1 = [0] * N
		self.find_children(root, adj, vis, s0, s1)
		return min(s0[root], s1[root])


class Solution:

	def countVertex(self, N, edges):
		nodes = {i: [] for i in range(1, N + 1)}
		temp = []
		for (i, j) in edges:
			nodes[i].append(j)
			nodes[j].append(i)
		sum = 0
		while sum < N:
			for i in list(nodes.keys())[::-1]:
				if len(nodes[i]) == 1:
					if nodes[i][0] not in temp:
						temp.append(nodes[i][0])
					if nodes[nodes[i][0]] != []:
						sum += 1
						nodes[nodes[i][0]] = []
					sum += 1
					nodes[i] = []
				elif len(nodes[i]) > 1:
					j = 0
					while j < len(nodes[i]):
						if nodes[nodes[i][j]] == []:
							nodes[i].remove(nodes[i][j])
						else:
							j += 1
					if nodes[i] == []:
						sum += 1
		return len(temp)


class Solution:

	def countVertex(self, N, edges):
		graph = {}
		for (a, b) in edges:
			if a in graph:
				graph[a].append(b)
			else:
				graph[a] = [b]
			if b in graph:
				graph[b].append(a)
			else:
				graph[b] = [a]
		count = [0]
		visited = [False for _ in range(0, N)]
		visited[0] = True
		self.dfs(1, visited, graph, count)
		return count[0]

	def dfs(self, node, visited, tree, c):
		children = tree[node]
		currSelected = False
		for child in children:
			if not visited[child - 1]:
				visited[child - 1] = True
				childSelected = self.dfs(child, visited, tree, c)
				if not childSelected:
					currSelected = True
		if currSelected:
			c[0] += 1
		return currSelected


class Solution:

	def f(self, adj, ind, par, dp):
		dp[ind][1] = 1
		for cld in adj[ind]:
			if cld != par:
				self.f(adj, cld, ind, dp)
				dp[ind][1] += min(dp[cld][1], dp[cld][0])
				dp[ind][0] += dp[cld][1]

	def countVertex(self, N, edges):
		adj = [[] for i in range(N)]
		for i in range(len(edges)):
			adj[edges[i][0] - 1] += [edges[i][1] - 1]
			adj[edges[i][1] - 1] += [edges[i][0] - 1]
		dp = [[0] * 2 for i in range(N)]
		self.f(adj, 0, -1, dp)
		return min(dp[0][0], dp[0][1])


from collections import defaultdict

class Solution:

	def countVertex(self, N, edges):
		treeGraph = defaultdict(lambda : [])
		totalEdges = len(edges)
		for edge in edges:
			treeGraph[edge[0]].append(edge[1])
			treeGraph[edge[1]].append(edge[0])
		self.getEdge(treeGraph)
		litEdges = 0
		nodeCount = 0
		while True:
			edge = self.getEdge(treeGraph)
			if edge is None:
				return nodeCount
			maxNode = treeGraph[edge][0]
			litEdges += len(treeGraph[maxNode])
			nodeCount += 1
			if litEdges < totalEdges:
				for node in treeGraph[maxNode]:
					treeGraph[node].remove(maxNode)
					if len(treeGraph[node]) == 0:
						treeGraph.pop(node)
				treeGraph.pop(maxNode)
			else:
				return nodeCount

	def getEdge(self, graph):
		for node in graph:
			if len(graph[node]) == 1:
				return node


class Solution:

	def builtTree(self, edges, N):
		tree = {i: [] for i in range(1, N + 1)}
		for (u, v) in edges:
			tree[u].append(v)
			tree[v].append(u)
		return tree

	def dfs(self, currNode, seen, tree):
		if currNode in seen:
			return (0, 0)
		seen.add(currNode)
		prevLight = prevNotLight = 0
		for child in tree[currNode]:
			res = self.dfs(child, seen, tree)
			prevLight += res[0]
			prevNotLight += min(res)
		return (prevNotLight + 1, prevLight)

	def countVertex(self, N, edges):
		tree = self.builtTree(edges, N)
		seen = set()
		return min(self.dfs(1, seen, tree))


class Solution:

	def dfs(self, i, adj):
		sel = False
		for ch in adj[i]:
			if not self.vis[ch]:
				self.vis[ch] = True
				chsel = self.dfs(ch, adj)
				if not chsel:
					sel = True
		if sel:
			self.count += 1
		return sel

	def countVertex(self, N, edges):
		self.count = 0
		adj = [[] for i in range(N + 1)]
		self.vis = [False for i in range(N + 1)]
		for i in edges:
			(u, v) = (i[0], i[1])
			adj[u].append(v)
			adj[v].append(u)
		self.vis[1] = True
		self.dfs(1, adj)
		return self.count


class Graph:

	def __init__(self, v):
		self.V = v
		self.l = [[] for __ in range(v)]
		self.lights = 0

	def addEdge(self, v1, v2):
		self.l[v1].append(v2)
		self.l[v2].append(v1)

	def bfs(self, v1, v2):
		visited = [0] * self.V
		que = queue.Queue()
		visited[v1] = 1
		que.put(v1)
		while not que.empty():
			p = que.queue[0]
			que.get()
			i = 0
			while i < len(self.l[p]):
				if not visited[self.l[p][i]]:
					visited[self.l[p][i]] = visited[p] + 1
					que.put(self.l[p][i])
				if self.l[p][i] == v2:
					return visited[self.l[p][i]] - 1
				i += 1

	def bfs_path_len(self, v):
		visited = [0] * self.V
		visited[v] = 1
		q = queue.Queue()
		q.put(v)
		ans = []
		print('self.l[%d]=%r' % (v, self.l[v]))
		sl = 1
		for i in range(len(self.l[v])):
			p = self.l[v][i]
			i = 1
			cl = sl
			while i < len(self.l[p]):
				cl += 1
				if not visited[self.l[p][i]]:
					print('l[%d][%d]=%d' % (p, i, self.l[p][i]))
					p = self.l[p][i]
					i = 0
					visited[self.l[p][i]] = 1
				else:
					print('visited[%d][%d]' % (p, i))
					i += 1
			print('cl=%d' % cl)
			ans.append(cl // 3 + 0 if cl % 3 == 0 else 1)
		print('ans=%r' % ans)
		return sum(ans)

	def dfs(self, visited, node):
		select = 0
		visited[node] = 1
		for i in self.l[node]:
			if not visited[i]:
				if not self.dfs(visited, i):
					select = 1
		if select:
			self.lights += 1
		return select

class Solution:

	def countVertex(self, N, edges):
		g = Graph(N + 1)
		for e in edges:
			g.addEdge(e[0], e[1])
		visited = [0] * (N + 1)
		g.dfs(visited, 1)
		return g.lights


class Solution:

	def countVertex(self, N, edges):
		Edges = {i: [] for i in range(1, N + 1)}
		for edge in edges:
			Edges[edge[0]].append(edge[1])
			Edges[edge[1]].append(edge[0])

		def Walker(point: int, par: int):
			res = [0, 1]
			for v in Edges[point]:
				if v != par:
					subres = Walker(v, point)
					res[0] += subres[1]
					res[1] += min(subres)
			return res
		(a, b) = edges[0]
		return min(Walker(a, -1))


class Solution:

	def countVertex(self, N, edges):
		count = 0

		def recur(node, graph, visited):
			nonlocal count
			visited[node] = True
			is_selected = False
			for neighbour in graph[node]:
				if not visited[neighbour]:
					is_child_selected = recur(neighbour, graph, visited)
					if not is_child_selected:
						is_selected = True
			if is_selected:
				count += 1
			return is_selected
		graph = {i: [] for i in range(1, N + 1)}
		visited = [False] * (N + 1)
		for (i, j) in edges:
			graph[i].append(j)
			graph[j].append(i)
		recur(1, graph, visited)
		return count


from collections import defaultdict

class Solution:

	def countVertex(self, N, edges):
		graph = [[] for i in range(N + 1)]
		for (u, v) in edges:
			graph[u].append(v)
			graph[v].append(u)
		ans = 0

		def dfs(node):
			nonlocal ans
			if vis[node]:
				return sel[node]
			vis[node] = True
			temp = False
			for i in graph[node]:
				if not vis[i] and (not dfs(i)):
					temp = True
			if temp:
				ans += 1
				return True
			return False
		vis = [False] * (N + 1)
		dfs(1)
		return ans


from heapq import heappush as hpush, heappop as hpop

class Solution:

	def countVertex(self, N, edges):
		adj = [[] for _ in range(N)]
		for (a, b) in edges:
			adj[a - 1].append(b - 1)
			adj[b - 1].append(a - 1)
		vis = [0] * N

		def dfs(i):
			vis[i] = 1
			temp = True
			for neigh in adj[i]:
				if vis[neigh]:
					continue
				temp &= dfs(neigh)
			if not temp:
				dfs.count += 1
				temp = True
			else:
				temp = False
			return temp
		dfs.count = 0
		for i in range(N):
			if not vis[i]:
				dfs(i)
		return dfs.count


from collections import defaultdict

class Solution:

	def countVertex(self, N, edges):
		count = [0]
		visited = [0] * (N + 1)
		adj = defaultdict(list)
		for (i, j) in edges:
			adj[i].append(j)
			adj[j].append(i)

		def dfs(node, adj, visited, count):
			visited[node] = 1
			select = False
			for child in adj[node]:
				if not visited[child] and (not dfs(child, adj, visited, count)):
					select = True
			if select:
				count[0] += 1
			return select
		dfs(1, adj, visited, count)
		return count[0]


class Solution:

	def countVertex(self, N, edges):
		Tree = [[] for i in range(N + 1)]
		visited = [False] * (N + 1)
		for (u, v) in edges:
			Tree[u].append(v)
			Tree[v].append(u)

		def DFS(node):
			visited[node] = True
			Selected = False
			for next_node in Tree[node]:
				if not visited[next_node] and (not DFS(next_node)):
					Selected = True
			if Selected:
				count[0] += 1
			return Selected
		count = [0]
		DFS(1)
		return count[0]


class Solution:
	count = 0

	def dfs(self, connected, visited, node):
		visited[node] = 1
		select = False
		for e in connected[node]:
			if visited[e] == 0:
				isChildLit = self.dfs(connected, visited, e)
				if not isChildLit:
					select = True
		if select:
			self.count += 1
		return select

	def countVertex(self, N, edges):
		nodes = [False for n in range(N + 1)]
		connects = [[] for n in range(N + 1)]
		for e in edges:
			idx = e[0]
			idy = e[1]
			connects[idx].append(idy)
			connects[idy].append(idx)
		self.dfs(connects, nodes, 1)
		return self.count


class Solution:

	def dfs(self, graph, u, p):
		(e, i) = (0, 1)
		for v in graph[u]:
			if v != p:
				(ce, ci) = self.dfs(graph, v, u)
				e += ci
				i += min(ci, ce)
		return (e, i)

	def countVertex(self, N, edges):
		graph = [[] for _ in range(N)]
		for (u, v) in edges:
			graph[u - 1].append(v - 1)
			graph[v - 1].append(u - 1)
		return min(self.dfs(graph, 0, -1))


class Solution:

	def fun(self, dp, u, par):
		(ex, ix) = (0, 1)
		for i in dp[u]:
			if i != par:
				(tex, tix) = self.fun(dp, i, u)
				ex = ex + tix
				ix = ix + min(tix, tex)
		return (ex, ix)

	def countVertex(self, N, edges):
		adj = [[] for _ in range(N)]
		for (i, j) in edges:
			adj[i - 1].append(j - 1)
			adj[j - 1].append(i - 1)
		return min(self.fun(adj, 0, -1))


class Solution:

	def countVertex(self, N, edges):
		count = [0]

		def minnodes(root):
			visited[root] = True
			for child in adj[root]:
				if visited[child] == False and select[child] == False and (minnodes(child) == False):
					select[root] = True
			if select[root]:
				count[0] += 1
			return select[root]
		adj = [[] for i in range(N + 1)]
		visited = [False for i in range(N + 1)]
		select = [False for i in range(N + 1)]
		for ele in edges:
			adj[ele[0]].append(ele[1])
			adj[ele[1]].append(ele[0])
		minnodes(1)
		return count[0]


class Solution:

	def countVertex(self, N, edges):
		adj = [[] for i in range(N)]
		for i in range(len(edges)):
			adj[edges[i][0] - 1].append(edges[i][1] - 1)
			adj[edges[i][1] - 1].append(edges[i][0] - 1)
		res = [0]
		visited = [False for i in range(N)]

		def solve(i, adj):
			visited[i] = True
			flag = False
			for j in adj[i]:
				if not visited[j]:
					curr = solve(j, adj)
					if not curr:
						flag = True
			if flag:
				res[0] += 1
			return flag
		for i in range(N):
			if not visited[i]:
				solve(i, adj)
		return res[0]