BFS implementation to find connected components taking too long This is in continuation to a question I asked here.  Given the total number of nodes (employees) and the adjacency list (friendship amongst employees), I need to find all the connected components.

public class Main {
    static HashMap&lt;String, Set&lt;String&gt;&gt; friendShips;

    public static void main(String[] args) throws IOException {
        BufferedReader  in= new BufferedReader(new InputStreamReader(System.in));

            String dataLine = in.readLine();
            String[] lineParts = dataLine.split(" ");
            int employeeCount = Integer.parseInt(lineParts[0]);
            int friendShipCount = Integer.parseInt(lineParts[1]);
            friendShips = new HashMap&lt;String, Set&lt;String&gt;&gt;();
            for (int i = 0; i &lt; friendShipCount; i++) {
                String friendShipLine = in.readLine();
                String[] friendParts = friendShipLine.split(" ");
                mapFriends(friendParts[0], friendParts[1], friendShips);
                mapFriends(friendParts[1], friendParts[0], friendShips);
            }
            Set&lt;String&gt; employees = new HashSet&lt;String&gt;();
            for (int i = 1; i &lt;= employeeCount; i++) {
                employees.add(Integer.toString(i));
            }
            Vector&lt;Set&lt;String&gt;&gt; friendBuckets = bucketizeEmployees(employees);
            System.out.println(friendBuckets.size());
    }

    public static void mapFriends(String friendA, String friendB, Map&lt;String, Set&lt;String&gt;&gt; friendsShipMap) {
        if (friendsShipMap.containsKey(friendA)) {
            friendsShipMap.get(friendA).add(friendB);
        } else {
            Set&lt;String&gt; friends = new HashSet&lt;String&gt;();
            friends.add(friendB);
            friendsShipMap.put(friendA, friends);
        }
    }

    public static Vector&lt;Set&lt;String&gt;&gt; bucketizeEmployees(Set&lt;String&gt; employees) {
        Vector&lt;Set&lt;String&gt;&gt; friendBuckets = new Vector&lt;Set&lt;String&gt;&gt;();
        while (!employees.isEmpty()) {
            String employee = getHeadElement(employees);
            Set&lt;String&gt; connectedEmployeesBucket = getConnectedFriends(employee);
            friendBuckets.add(connectedEmployeesBucket);
            employees.removeAll(connectedEmployeesBucket);
        }
        return friendBuckets;
    }

    private static Set&lt;String&gt; getConnectedFriends(String friend) {
        Set&lt;String&gt; connectedFriends = new HashSet&lt;String&gt;();
        connectedFriends.add(friend);
        Set&lt;String&gt; queuedFriends = new LinkedHashSet&lt;String&gt;();
        if (friendShips.get(friend) != null) {
            queuedFriends.addAll(friendShips.get(friend));
        }
        while (!queuedFriends.isEmpty()) {
            String poppedFriend = getHeadElement(queuedFriends);
            connectedFriends.add(poppedFriend);
            if (friendShips.containsKey(poppedFriend))
                for (String directFriend : friendShips.get(poppedFriend)) {
                    if (!connectedFriends.contains(directFriend) &amp;&amp; !queuedFriends.contains(directFriend)) {
                        queuedFriends.add(directFriend);
                    }
                }
        }
        return connectedFriends;
    }

    private static String getHeadElement(Set&lt;String&gt; setFriends) {
        Iterator&lt;String&gt; iter = setFriends.iterator();
        String head = iter.next();
        iter.remove();
        return head;
    }
}


I have tested my code using the following script, the results of which I consume as sdtIn

#!/bin/bash
echo "100000 100000"
for i in {1..100000}
do
    r1=$(( $RANDOM % 100000 ))
    r2=$(( $RANDOM % 100000 ))
    echo "$r1 $r2"
   done


While I was able to verify (for trivial inputs) that my answer is correct, when I try with huge inputs as with the above script, I see that the run takes long (~20s).

Is there anything I can do better in my implementation ?
First of all, two things to read or search for: Cluster analysis (just a hint, I'm not an expert about that) and Linked: The New Science of Networks by Albert-László Barabási. 

Barabási in his book shows that networks usually have some nodes which have a lot more connections than the others. The distribution is not the same in the real world as the sample shell script generates.
The code is quite good, I like your variable and method names and separated methods. I wonder why haven't anyone reviewed it yet.

Vector&lt;Set&lt;String&gt;&gt; friendBuckets = bucketizeEmployees(employees);



I'd use a simple List or ArrayList here. Vector is considered obsolete.
In the getConnectedFriends method the


Set&lt;String&gt; queuedFriends = new LinkedHashSet&lt;String&gt;();



could be a Queue. It has a poll method. As far as I tested it's faster than the currently used iterator-based remove.

public class Main {



Main isn't a good class name. Everyone can have a Main. What's it purpose? Try to find a more descriptive name.

static HashMap&lt;String, Set&lt;String&gt;&gt; friendShips;    



HashMap&lt;...&gt; reference types should be simply Map&lt;...&gt;. See: Effective Java, 2nd edition, Item 52: Refer to objects by their interfaces

Should I always use the private access modifier for class fields?; Item 13 of Effective Java 2nd Edition: Minimize the accessibility of classes and members.

 static HashMap&lt;String, Set&lt;String&gt;&gt; friendShips;    



Instead of Map&lt;String, Set&lt;String&gt;&gt; you could use Guava's Multimap (doc, javadoc) which was designed exactly for that. It would reduce the size of the mapFriends method:

public static void mapFriends(final String friendA, final String friendB,
        final Multimap&lt;String, String&gt; friendsShipMap) {
    friendsShipMap.put(friendA, friendB);
}


So, it could be removed.

public static Vector&lt;Set&lt;String&gt;&gt; bucketizeEmployees(Set&lt;String&gt; employees) {
    ...
}



This method calls getConnectedFriends(employee), which is the following:


private static Set&lt;String&gt; getConnectedFriends(String friend) {
    ...
}



It's confusing: what is the difference between an employee and friend? Are they the same?

if (friendShips.get(friend) != null) {



The following is the same:

if (friendShips.containsKey(friend)) {


A guard clause would be even better.

if (!friendShips.containsKey(friend)) {
    return connectedFriends;
}


if (!connectedFriends.contains(directFriend) &amp;&amp; !queuedFriends.contains(directFriend)) {
    queuedFriends.add(directFriend);
}



The !queuedFriends.contains(directFriend) condition is unnecessary, it's a set which can't contain elements twice and adding an already added element to a LinkedHashSet doesn't modify anything. From the javadoc:


  Note that insertion order is not affected if an element is re-inserted into the set.

The following pattern occurs more than once in the code:

if (map.containsKey(key)) {
    String value = map.get(key);
    ...
}
...


It might be a microoptimization, but if you profile the code and the results shows it as a bottleneck the following structure is the same:

String value = map.get(key);        
if (value != null) {
    ...
}
...

A few guard clause would help to make getConnectedFriends more flatten:

while (!queuedFriends.isEmpty()) {
    final String poppedFriend = getHeadElement(queuedFriends);
    connectedFriends.add(poppedFriend);
    if (!friendShips.containsKey(poppedFriend)) {
        continue;
    }
    for (final String directFriend: friendShips.get(poppedFriend)) {
        if (connectedFriends.contains(directFriend)) {
            continue;
        }
        queuedFriends.add(directFriend);
    }
}