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

Question

我正在解决以下问题:

在有人的房间里,如果他们是直接或间接的朋友,我们将定义两个人是朋友.如果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<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;
  }

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

Answer 1

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

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

• 首先,将"朋友组"计算为不相交的数据结构:
  • 初始化一个不相交的数据结构,其中集合的元素将是房间中的人.
  • 对于每个人p的房间:
    • 调用MakeSet(p)初始化一个只包含该人的"朋友组".
  • 对于每个直接友谊p ₁ ↔ p ₂:
    • 呼叫联盟(第₁ 页,第₂ 页)统一包含p ₁的"朋友组" 和包含p _2的朋友.
• 接下来,计算"朋友组"的大小作为地图:
  • 初始化地图,其中键将是房间中的一些人(即,他们各自的"朋友组"的代表),并且值将是数字(即,各种"朋友组"的大小).
  • 对于房间里的每个人p ₁:
    • 调用查找(第₁ 页)以查找该人的"朋友组" 的代表p ₂.
    • 如果映射尚未包含键p ₂的值,请为该键插入值0.
    • 增加键p ₂的值.
• 最后,计算结果:
  • 将结果初始化为较大的值,例如房间中的人数.
  • 对于地图中的每个值(="朋友组"的大小):
    • 如果此值小于结果,则将结果设置为等于此值.
  • 返回结果.

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