131. Count Number of Unconnected Trees in a Forest
Count Number of Unconnected Trees in a Forest
Given a list of Child->Parent relations in a forest, find the number of unconnected trees.
Each relation represents a directed edge from a child node to its parent node. The input describes a valid forest, which means there may be one or more separate trees and there are no cycles.
The answer is the number of distinct trees formed by all nodes that appear in the given relations. Equivalently, this is the number of distinct root nodes in the forest.
Method Signature
int countUnconnectedTrees(List<String> relations)
- Each string in
relations is in the format "child,parent".
child and parent are integer node values.- A child points to exactly one parent in a relation.
- The input forms a valid forest, so there are no cycles.
- The method returns the number of disconnected trees present in the forest.
Input Format
relations is a List<String>.- Each element is a relation such as
"2,1", which means node 2 has parent 1.
Return Format
- Return an
int representing the number of unconnected trees.
Constraints
0 ≤ relations.size() ≤ 100,000- Each relation string is in the format
"child,parent"
1 ≤ child, parent ≤ 10^9child != parent- Each child appears in at most one relation as a child.
- The given relations form a valid forest with no cycles.
- If
relations is empty, return 0.
Examples
Example 1
countUnconnectedTrees(relations = List.of("2,1", "3,1", "5,4", "6,4")) returns 2
Explanation: One tree has root 1 with children 2 and 3. Another tree has root 4 with children 5 and 6.
Example 2
countUnconnectedTrees(relations = List.of("2,1", "3,2", "4,3")) returns 1
Explanation: All nodes belong to a single chain ending at root 1, so there is only one tree.
Example 3
countUnconnectedTrees(relations = List.of("2,1", "4,3", "6,5", "7,5")) returns 3
Explanation: The three roots are 1, 3, and 5, so there are three separate trees.
Example 4
countUnconnectedTrees(relations = List.of()) returns 0
Explanation: No relations are given, so no tree can be formed from the input.