java - 从圈子里找一小群 friend ？

Question

我正在解决以下问题:

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..

例子:输入:

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

Is there any better way to solve this problem?

更好的方法是使用 disjoint-set data structure :

• 首先，将“ friend 组”计算为不相交集的数据结构:
  • 初始化一个不相交的集合数据结构，其中集合的元素将是房间里的人。
  • 对于房间中的每个人 p:
    • 调用 MakeSet(p) 来初始化只包含那个人的“ friend 组”。
  • 对于每个直接友谊p₁↔p₂:
    • 调用Union(p₁, p₂) 来统一包含 p₁ 和包含 p₂ 的“一群 friend ”。
• 接下来，将“ friend 组”的大小计算为 map :
  • 初始化一个 map ，其中键是房间中的一些人(即他们各自“ friend 组”的代表)，值是数字(即各种“ friend 组”的大小").
  • 对于房间中的每个人 p₁:
    • 调用Find(p₁)寻找代表p₂该人的“ friend 群”。
    • 如果映射尚未包含键 p₂ 的值，请为该键插入值 0。
    • 增加键 p₂ 的值。
• 最后，计算结果:
  • 将结果初始化为一个较大的值，例如房间里的人数。
  • 对于 map 中的每个值(=“ friend 组”的大小):
    • 如果此值小于结果，则将结果设置为等于此值。
  • 返回结果。

顺便说一下，您正在执行的操作的技术名称是 transitive closure :“是 friend ”关系是“直接是 friend ”关系的传递闭包。 (但是，维基百科文章中描述的算法对于您的问题来说并不是最佳的，因为它们没有利用您的关系是 symmetric 的事实。)