← 返回 openai 的题目列表Count Machines in a Cluster Tree and Recover Tree Topology
类型：online_judge
Problem: Count Machines in a Cluster Tree and Recover Tree Topology
A compute cluster consists of multiple machines. Their management relationships form a rooted tree. The root is the entry machine, and each directed edge parent -> child means parent can access one direct child machine.
Implement a program that does two things:
Count the total number of machines reachable from the root.
Print the topology of the reachable tree: for each reachable node in ascending order, print its direct children in ascending order.
Input Format
n m root
parent1 child1
parent2 child2
...
parentm childm
n: number of machines, labeled from 0 to n - 1.
m: number of directed parent-child edges.
root: root machine id.
The next m lines each contain two integers parent child.
Output Format
The first line should be the number of machines reachable from root.
Then print the topology for every reachable node in ascending node-id order:
node: child1 child2 ...
If a node has no children, print:
node:
Constraints
1 <= n <= 100000
0 <= m <= 100000
0 <= root < n
The input may contain nodes unreachable from the root.
Duplicate edges should be deduplicated.
If the input is not a strict tree and contains cycles or nodes with multiple parents, still count only nodes first reached from root using DFS/BFS, and avoid infinite loops.
Example
Input:
7 6 0
0 1
0 2
1 3
1 4
2 5
2 6
Output:
7
0: 1 2
1: 3 4
2: 5 6
3:
4:
5:
6:
Example
Input
7 6 0
0 1
0 2
1 3
1 4
2 5
2 6
Output
7
0: 1 2
1: 3 4
2: 5 6
3:
4:
5:
6: