0. Friends Graph

/*
Given:
array of relationships -  ["A:B", "B:C", "D:E"]
array of names for whom friends count should be found based on relationships.

Example:
  relationships -  ["A:B", "B:C", "D:E"]. =>  A-B-C D-E
  names - ["A", "E"]

  answer is "A": 2, "E": 1

Idea:
Relationships - ориентированный двунаправленный граф.
Ищем компоненты связности (группы друзей) в грфе через DFS.
*/


import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Optional;
import java.util.Set;
import java.util.stream.Collectors;

public class FriendsGraphSolution {
    private static final Integer NOT_DEFINED_GROUP = -1;

    public Map<String, Integer> numberOfFriends(String[] relationships, String[] names) {
        Map<String, Integer> friendsMap = new HashMap<>();
        Map<String, Set<String>> friendsGraph = new HashMap<>();
        Map<String, Integer> friendsGroups = new HashMap<>();

        int groupNumber = 0;

        // init bidirectional graph of friends
        Arrays.asList(relationships).forEach(rel -> {
            String[] relationship = rel.split(":");

            String from = relationship[0];
            String to = relationship[1];

            Set<String> toSet = friendsGraph.getOrDefault(from, new HashSet<>());
            toSet.add(to);
            toSet.remove(from);
            friendsGraph.put(from, toSet);

            Set<String> fromSet = friendsGraph.getOrDefault(to, new HashSet<>());
            fromSet.add(from);
            fromSet.remove(to);
            friendsGraph.put(to, fromSet);

            friendsGroups.put(from, NOT_DEFINED_GROUP);
            friendsGroups.put(to, NOT_DEFINED_GROUP);
        });


        // group friends via dfs
        for (String friend : friendsGroups.keySet()) {
            if (NOT_DEFINED_GROUP.equals(friendsGroups.get(friend))) {
                dfsAndGroup(friend, friendsGraph, friendsGroups, ++groupNumber);
            }
        }

        Map<Integer, Long> groupsSizes = friendsGroups.values()
                .stream()
                .collect(Collectors.groupingBy(group -> group, HashMap::new, Collectors.counting()));

        Arrays.asList(names).forEach(name -> {
            int group = friendsGroups.get(name);
            int groupSize = groupsSizes.get(group).intValue();
            friendsMap.put(name, groupSize - 1);
        });

        return friendsMap;
    }

    private void dfsAndGroup(String vertex, Map<String, Set<String>> friendsGraphMap,
                             Map<String, Integer> vertexGroups, int groupNumber) {
        if (!NOT_DEFINED_GROUP.equals(vertexGroups.get(vertex))) {
            return;
        }

        vertexGroups.put(vertex, groupNumber);

        Optional.ofNullable(friendsGraphMap.get(vertex))
                .orElse(Collections.emptySet())
                .forEach(friend -> dfsAndGroup(friend, friendsGraphMap, vertexGroups, groupNumber));

    }
}

---------

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import org.junit.Assert;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.MethodSource;
import ru.ilka.leetcode.solution.FriendsGraphSolution;

import java.util.Map;
import java.util.stream.Stream;

public class FriendsGraphSolutionTest {

    private FriendsGraphSolution friendsGraphSolution = new FriendsGraphSolution();

    private static Stream<SolutionTestArgs> argumentsProvider() {
        return Stream.of(SolutionTestArgs.builder()
                        .relationships(new String[]{"Vanja:Sergio", "Sergio:Pedro", "Pedro:Martin", "Martin:Pablo",
                                "Pablo:Sergio", "Jelena:Ivan", "Jelena:Alan", "Alan:Tomislav"})
                        .names(new String[]{"Tomislav", "Martin"})
                        .result(Map.of("Tomislav", 3, "Martin", 4))
                        .build(),
                SolutionTestArgs.builder()
                        .relationships(new String[]{"Alvaro:Alex", "Roman:Nikola", "Octavia:Barbara", "Joao:Marko",
                                "Luis:Vanja", "Gabriel:Gustavo", "Alan:Pablo", "Ivan:Andres", "Artem:Anne",
                                "Martin:Alessandro", "Sebastian:Vinny", "Eduardo:Francis", "Zoltan:Vlad"})
                        .names(new String[]{"Zoltan", "Ivan"})
                        .result(Map.of("Zoltan", 1, "Ivan", 1))
                        .build(),
                SolutionTestArgs.builder()
                        .relationships(new String[]{"David:Francis", "Francis:Alessandro", "Alessandro:Ivan",
                                "Tomislav:Ivan", "Anne:Tomislav", "Anne:David", "Francis:Tomislav"})
                        .names(new String[]{"Francis", "David"})
                        .result(Map.of("Francis", 5, "David", 5))
                        .build(),
                SolutionTestArgs.builder()
                        .relationships(new String[]{"Alessandro:Anna", "Anna:Anne", "Anne:Barbara", "Barbara:David",
                                "David:Francis", "Francis:Eduardo", "Eduardo:Anna", "Eduardo:Alessandro",
                                "Luis:Marko", "Joao:Vlad", "Vlad:Luka", "Luka:Nikola", "Nikola:Roman",
                                "Vlad:Roman", "Vlad:Vinny", "Vinny:Roman", "Vlad:Andres", "Vinny:Ivan"})
                        .names(new String[]{"Barbara", "Joao"})
                        .result(Map.of("Barbara", 6, "Joao", 7))
                        .build()
        );
    }

    @ParameterizedTest(name = "attributes: {0}")
    @MethodSource("argumentsProvider")
    public void solutionTest(SolutionTestArgs args) {
        Assert.assertEquals(friendsGraphSolution.numberOfFriends(args.getRelationships(), args.getNames()),
                args.getResult());
    }

    @Data
    @Builder
    @AllArgsConstructor
    static class SolutionTestArgs {
        String[] relationships;
        String[] names;
        Map<String, Integer> result;
    }
}