find a smaller group of friends from the circle?

Question

I am working on the following problem:

In a room with people, we will define two persons are friends if they are directly or indirectly friends. If A is a friend with B, and B is a friend with C, then A is a friend of C too. A group of friends is a group of persons where any two persons in the group are friends. Given the list of persons that are directly friends, find the smallest group of friends..

Example: Input:

1<->6 
2<->7
3<->8
4<->9
2<->6
3<->5

Groups:

1-6-2-7
3-8-5
4-9

The number of people in the smallest group is 2 i.e. 4-9 so we should return 2.

I came up with the code below but I don't understand how to use this holder map now to get the required output. I am kinda confused here. What is the best way to solve this problem?

  private static int findGroups(final List<List<Integer>> inputs) {
    if (inputs == null || inputs.isEmpty()) {
      return 0;
    }
    int count = Integer.MAX_VALUE;

    Map<Integer, List<Integer>> holder = new HashMap<>();
    for (List<Integer> input : inputs) {
      // storing it in bidirectional way in the map
      List<Integer> l =
          holder.containsKey(input.get(0)) ? holder.get(input.get(0)) : new ArrayList<Integer>();
      l.add(input.get(1));
      holder.put(input.get(0), l);

      List<Integer> l1 =
          holder.containsKey(input.get(1)) ? holder.get(input.get(1)) : new ArrayList<Integer>();
      l1.add(input.get(0));
      holder.put(input.get(1), l1);
    }
    System.out.println(holder);

    // use holder map to get the smaller group here?

    return count;
  }

Looks like I need to use recursion here to get smaller groups?

Answer 1

Is there any better way to solve this problem?

A better approach is to use a disjoint-set data structure:

• First, compute the "groups of friends" as a disjoint-set data structure:
  • Initialize a disjoint-set data structure where the elements of the sets will be the people in the room.
  • For each person p in the room:
    • Call MakeSet(p) to initialize a "group of friends" containing just that person.
  • For each direct friendship p₁↔p₂:
    • Call Union(p₁, p₂) to unify the "group of friends" that contains p₁ with the one that contains p₂.
• Next, compute the sizes of the "groups of friends" as a map:
  • Initialize a map where the keys will be some of the people in the room (namely, the representatives of their respective "groups of friends") and the values will be numbers (namely, the sizes of the various "groups of friends").
  • For each person p₁ in the room:
    • Call Find(p₁) to find the representative p₂ of that person's "group of friends".
    • If the map does not already contain a value for the key p₂, insert the value 0 for that key.
    • Increment the value for the key p₂.
• Lastly, compute the result:
  • Initialize a result to a large value, e.g. the number of people in the room.
  • For each value (= size of a "group of friends") in the map:
    • If this value is less than the result, set the result equal to this value.
  • Return the result.

By the way, the technical name for the operation you're performing is transitive closure: the "are friends" relation is the transitive closure of the "are directly friends" relation. (However, the algorithms described at the Wikipedia article for that are not optimal for your problem, because they don't take advantage of the fact that your relation is symmetric.)