从圈子中找到一小群朋友？

我正在解决以下问题:

在有人的房间里,如果他们是直接或间接的朋友,我们将定义两个人是朋友.如果A是B的朋友,B是C的朋友,那么A也是C的朋友.一群朋友是这群人中任何两个人都是朋友的一群人.给出直接朋友的人名单,找到最小的朋友群.

示例:输入:

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

团体:

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

最小组中的人数是2,即4-9,所以我们应该返回2.

我想出了下面的代码,但我现在不明白如何使用这个holder地图来获得所需的输出.我在这里有点困惑.解决这个问题的最佳方法是什么？

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

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

      List l1 =
          holder.containsKey(input.get(1)) ? holder.get(input.get(1)) : new ArrayList();
      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;
  }

看起来我需要在这里使用递归来获得更小的组？

有没有更好的方法来解决这个问题？

更好的方法是使用不相交的数据结构:

首先,将"朋友组"计算为不相交的数据结构:

初始化一个不相交的数据结构,其中集合的元素将是房间中的人.

对于每个人p的房间:

调用MakeSet(p)初始化一个只包含该人的"朋友组".

对于每个直接友谊p ₁ ↔ p ₂:

呼叫联盟(第₁ 页,第₂ 页)统一包含p ₁的"朋友组" 和包含p _2的朋友.

接下来,计算"朋友组"的大小作为地图:

初始化地图,其中键将是房间中的一些人(即,他们各自的"朋友组"的代表),并且值将是数字(即,各种"朋友组"的大小).

对于房间里的每个人p ₁:

调用查找(第₁ 页)以查找该人的"朋友组" 的代表p ₂.

如果映射尚未包含键p ₂的值,请为该键插入值0.

增加键p ₂的值.

最后,计算结果:

将结果初始化为较大的值,例如房间中的人数.

对于地图中的每个值(="朋友组"的大小):

如果此值小于结果,则将结果设置为等于此值.

返回结果.

顺便说一句,你正在进行的操作的技术名称是传递性的封闭:"是朋友"的关系是"直接朋友"关系的传递性封闭.(但是,维基百科文章中描述的算法并不适用于您的问题,因为它们没有利用您的关系是对称的这一事实.)