Help with 2 problems - open to bidding

The ski season is almost over (sigh) and the ski resort where you were scheduling lessons has now put you in charge of organizing a spring hike. You are given a pile of n identical-looking walkie-talkies. Even though they look identical, they are not all the same inside, and not all compatible. You have only one method of testing compatibility: turn two walkie-talkies on and test if you can get a signal from one to the other. (However, compatibility is reflexive, symmetric, and transitive, so if you tested A against B and found them compatible, and then tested B against C and found them compatible, then you know the triple A, B, C is mutually compatible.) You know that there exist more than n/2 walkie-talkies in the pile that are all mutually com- patible. Describe an algorithm to find them in O(nlogn) time, so you can use them on the hike. Prove that your algorithm is correct and runs in O(nlogn) time (note: a linear-time algorithm is also possible, but is harder to find).