1. When a vertex and its incident edges are removed from a tree, a collection of sub- trees remains. Give a linear-time algorithm that ?nds a vertex whose removal from an N vertex tree leaves no subtree with more than N/2 vertices.
2. Give a linear-time algorithm to determine the longest unweighted path in an acyclic undirected graph (that is, a tree).
3. Consider an N-by-N grid in which some squares are occupied by black circles. Two squares belong to the same group if they share a common edge. In Figure 9.88, there is one group of four occupied squares, three groups of two occupied squares, and two individual occupied squares. Assume that the grid is represented by a two-dimensional array. Write a program that does the following:
a. Computes the size of a group when a square in the group is given.
b. Computes the number of different groups.
c. Lists all groups.