найти меньшую группу друзей из круга?

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

Вот код, который я написал из любопытства по поводу вашей проблемы. Я не знаю много о графиках, но он использует рекурсию, как вы и просили.

В основном вы проходите ввод и для каждого человека вы создаете ArrayList<Integer>. В этом массиве люди, которые являются непосредственными друзьями этого человека. Например, для 1: {6}, for 2: {7, 6}, for 3: {8, 5}. Затем, чтобы получить всех друзей человека 2, вы создаете массив compoud ArrayList<Integer>, собирая массивы для людей 7 и 6 (исключая дубликаты). Таким образом, рекурсия может использоваться таким образом, что функция getAllFriends(Integer person) должна будет возвращать getAllFriends(Integer person2) и для ближайших друзей этого человека.

Итак, код может выглядеть примерно так:

public class Test  {
        public static void main(String[] args) throws Exception {
            String input = "1<->6\n" +
            "2<->7\n" +
            "3<->8\n" +
            "4<->9\n" +
            "2<->6\n" +
            "3<->5";

            HashMap<Integer, ArrayList<Integer>> friends = processInput(input);  //getting data from the input string and storing it in a structured way
            System.out.println(getAllFriends(1, friends, new ArrayList<Integer>(){{add(1);}}));  //output: [1, 6, 2, 7]. Double brackets create an anonymous inner class, you add to the result the id of a person whose friends you're collecting
            }

        public static HashMap<Integer, ArrayList<Integer>> processInput(String input) throws Exception  {
            HashMap<Integer, ArrayList<Integer>> result = new HashMap<>();

            BufferedReader bufReader = new BufferedReader(new StringReader(input));
            String line=null;
            while( (line=bufReader.readLine()) != null )
            {
                Integer personLeft =  Integer.valueOf(line.substring(0, line.indexOf("<")));
                Integer personRight =Integer.valueOf(line.substring(line.indexOf(">")+1, line.length()));

                System.out.println(personLeft + ": " + personRight);

                if (!result.containsKey(personLeft))  {
                    result.put(personLeft, new ArrayList<Integer>());
                }

                result.get(personLeft).add(personRight);

                if (!result.containsKey(personRight))  {
                    result.put(personRight, new ArrayList<Integer>());
                }

                result.get(personRight).add(personLeft);
            }


            return result;

        }

        public static ArrayList<Integer>  getAllFriends(Integer person, HashMap<Integer, ArrayList<Integer>> friends, ArrayList<Integer> result)  {
            for (Integer personFriend: friends.get(person))  {
                    if (!result.contains(personFriend))  {
                        result.add(personFriend);  //add a person, if it wasn't added before
                        getAllFriends(personFriend, friends, result);  //check out that person's friends
                    }
            }

            return result;
        }
}   

Answer 2

Есть ли лучший способ решить эту проблему?

Лучшим подходом является использование структуры данных с несвязанными множествами :

• Сначала вычислите «группы друзей» как структуру данных с непересекающимися наборами:
  • Инициализируйте структуру данных по непересекающимся наборам, где элементами наборов будут люди в комнате.
  • Для каждого человека p в комнате:
    • Позвоните MakeSet ( p ), чтобы инициализировать "группу друзей", содержащую толькоэтот человек.
  • За каждую прямую дружбу p ₁ ↔ p ₂ :
    • Позвоните Союз ( p ₁ , p ₂ ) для объединения "группыдрузья ", который содержит p ₁ с тем, который содержит p ₂ .
• Затем вычислите размеры «групп друзей» как карту:
  • Инициализируйте карту, где kею будут некоторые люди в комнате (а именно, представители их соответствующих «групп друзей»), а значения будут числами (а именно, размерами различных «групп друзей»).
  • Для каждого человека р ₁ в комнате:
    • Звонок Найти ( р ₁ ) найти представителя p ₂"группы друзей" этого человека.
    • Если на карте еще нет значения для ключа p ₂ , введите значение 0 для этой клавиши.
    • Увеличьте значение для ключа p ₂ .
• Наконец, вычислите результат:
  • Инициализируйте результат большим значением, например количеством людей в комнате.
  • Для каждого значения (= размер «группы друзей») на карте:
    • Если это значение меньше результата, установите результат равным этому значению.
  • Вернуть результат.

Кстати, техническое имя выполняемой вами операции: транзитивное замыкание : отношение "друзья" - это транзитивное замыканиеотношения непосредственно друзей.(Однако алгоритмы, описанные в статье Википедии для этого, не являются оптимальными для вашей проблемы, потому что они не используют тот факт, что ваше отношение является симметричным .)