#11503 - Virtual Friends
|Algorithms Used:||other graph|
|Solution Description: ||This is a fairly standard union-find problem with two extra pieces. Firstly, you'll need to use a hash table to map nodes to their set leaders. Also, you need to keep track of the "size" of all set leaders. By size, I mean the number of elements in the set that the leader leads.|
Whenever you union two elements, first check if they're in the same set. If they are, do nothing. If not, get the sizes of both set leaders, and sum them. This will be the size of the new set leader.
Copyright 2008 (c) QuestToSolve.Com - Graphs Powered By