申論題

13. (15 points) A disjoint-set data structure supports two operations. One is UNION(z,y), which merges the two roots of the trees containing a and y. The other is FIND(z), which returns the root of the tree containing 2. Union-by-beight is a union heuristic, which keeps track of the heights of the trees to attach the shorter tree to the root of the taller tree.

(a) (9 points) Given an undirected graph G = (V,E), where V = {u₁,...u_m} (m ＞ 0) and E = {e₁,...，en) (n ＞ 0), devise an algorithm to check if the graph G is a tree or not by using UNION(ui,uj) with union-by-height and FIND(uk) with no path com pression, where Ui,Us and U_k V. Clearly describe your solution and analyze the tinre cumplexity of your algorithm in the worst case. No code is required (code will not be graded).