本文共 3673 字,大约阅读时间需要 12 分钟。
A graph G = (V, E) is a data structure where V is a finite set of vertices and E is a binary relation on V represented by a set of edges. Fig. 1 illustrates an example of a graph (or graphs).
Fig. 1A free tree is a connnected, acyclic, undirected graph. A rooted tree is a free tree in which one of the vertices is distinguished from the others. A vertex of a rooted tree is called "node."
Your task is to write a program which reports the following information for each node u of a given rooted tree T:
If the last edge on the path from the root r of a tree T to a node x is (p, x), then p is the parent of x, and x is a child of p. The root is the only node in T with no parent.
A node with no children is an external node or leaf. A nonleaf node is an internal node
The number of children of a node x in a rooted tree T is called the degree of x.
The length of the path from the root r to a node x is the depth of x in T.
Here, the given tree consists of n nodes and evey node has a unique ID from 0 to n-1.
Fig. 2 shows an example of rooted trees where ID of each node is indicated by a number in a circle (node). The example corresponds to the first sample input.
Fig. 2The first line of the input includes an integer n, the number of nodes of the tree.
In the next n lines, the information of each node u is given in the following format:
id k c1 c2 ... ck
where id is the node ID of u, k is the degree of u, c1 ... ck are node IDs of 1st, ... kth child of u. If the node does not have a child, the k is 0.
Print the information of each node in the following format ordered by IDs:
node id: parent = p , depth = d, type, [c1...ck]
p is ID of its parent. If the node does not have a parent, print -1.
d is depth of the node.
type is a type of nodes represented by a string (root, internal node or leaf). If the root can be considered as a leaf or an internal node, print root.
c1...ck is the list of children as a ordered tree.
Please follow the format presented in a sample output below.
130 3 1 4 101 2 2 32 03 04 3 5 6 75 06 07 2 8 98 09 010 2 11 1211 012 0
node 0: parent = -1, depth = 0, root, [1, 4, 10]node 1: parent = 0, depth = 1, internal node, [2, 3]node 2: parent = 1, depth = 2, leaf, []node 3: parent = 1, depth = 2, leaf, []node 4: parent = 0, depth = 1, internal node, [5, 6, 7]node 5: parent = 4, depth = 2, leaf, []node 6: parent = 4, depth = 2, leaf, []node 7: parent = 4, depth = 2, internal node, [8, 9]node 8: parent = 7, depth = 3, leaf, []node 9: parent = 7, depth = 3, leaf, []node 10: parent = 0, depth = 1, internal node, [11, 12]node 11: parent = 10, depth = 2, leaf, []node 12: parent = 10, depth = 2, leaf, []
41 3 3 2 00 03 02 0
node 0: parent = 1, depth = 1, leaf, []node 1: parent = -1, depth = 0, root, [3, 2, 0]node 2: parent = 1, depth = 1, leaf, []node 3: parent = 1, depth = 1, leaf, []
You can use a left-child, right-sibling representation to implement a tree which has the following data:
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. The MIT Press.
此题还是挺简单的, 判断节点是什么类型的只要判断是否有父亲和儿子就可以确定, 而求深度可以通过递归来实现。
代码如下:
#include#include #include #include #include using namespace std;const int maxn=100005;struct tree{ int parent; vector child; int depth;};tree node[maxn];int n;void init(){ for (int i=0;i
转载地址:http://epaen.baihongyu.com/