mediumTreesPattern: BFS
Minimum Domination Set Solution
Problem Statement
Given a tree represented as an adjacency list where each key is a node and its corresponding value is a list of its neighboring nodes, find the minimum number of nodes that need to be selected such that every node in the tree is either selected or adjacent to a selected node.
Examples
Example 1:
Input:{"1":["2","3"],"2":["1","4"],"3":["1","4"],"4":["2","3"]}
Output:1
Explanation: Selecting node 1 covers all nodes in the tree, as it is part of the tree and all nodes are connected.
Example 2:
Input:{"1":["2"],"2":["1","3"],"3":["2"]}
Output:1
Explanation: Selecting node 2 covers all nodes in the tree, as it is adjacent to both nodes 1 and 3.
Constraints
- The input tree is connected and has at least one node.
- The input tree has at most 100 nodes.
- Each node has at most 10 neighboring nodes.
- The input tree does not contain self-loops or parallel edges.
- The input is represented as an adjacency list where each key is a string representing a node and its corresponding value is a list of strings representing its neighboring nodes.
Time: O(n) Space: O(n)
An optimized approach involves using a greedy algorithm or dynamic programming to find the minimum dominating set in the tree. This approach works by selecting nodes in a way that maximizes the number of newly dominated nodes at each step, and can be implemented using a depth-first search or breadth-first search traversal of the tree with a time complexity of O(n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
from collections import defaultdict
tree = defaultdict(list)
minNodes = float("inf")
def dfs(node, parent, selected):
global minNodes
count = 0
for child in tree[node]:
if child != parent:
count += dfs(child, node, not selected)
if not selected:
return count
return min(count + 1, count)
n = int(sys.stdin.readline().strip())
for _ in range(n - 1):
u, v = map(int, sys.stdin.readline().strip().split())
tree[u].append(v)
tree[v].append(u)
minNodes = dfs(1, -1, False)
print(minNodes)