Problem: given a set of directed edges where both nodes of an edge are denoted by integers. Determine is such graph is a tree. Size: the number of edges and the size of the integer label of any node are not specified.
Assume the label of any node is less then 2^16. Use a set of integer pairs to store edges, and then collect the set of nodes from edges. To determine a tree, check that: number of edges + 1 = number of nodes. Secondly, find the unique root. Then perform tree search and check all nodes are reachable from the root. Finally, do remember that a empty tree has no node nor edge.
Notice: I guess the test data is small because of the running time is short, therefore, array and linear search are fast enough to perform set operations.
No comments:
Post a Comment