Need an answer to question 5.

4. (30 points) Given a weighted graph, we can use kruskal's algorithm to compute its MST within (rn log n) time, where rn is the number of edges and n is the number of vertices. But consider a special case: there are only two possible weights for all the edges (e.g., the weight could be either 1 or 2), can we design a linear time (i.e., (n + m)) algorithm for MST? (hint: you may consider BFS). 5. (bonus for extra 20 points) Consider a generalization of the above question 4: there are t 2 2 possible weights for all the edges (e.g., the weight could be 1, 2, ..., t), and we assume t is a small constant. Can we design a linear time (i.e., (n + m)) algorithm for MST