https://www.hackerrank.com/challenges/torque-and-development/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=graphs

RoadsAndLibraries.java

package com.github.jonathanlalou.exercices;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class RoadsAndLibraries {
    /*
     * Complete the 'roadsAndLibraries' function below.
     *
     * The function is expected to return a LONG_INTEGER.
     * The function accepts following parameters:
     *  1. INTEGER n
     *  2. INTEGER c_lib
     *  3. INTEGER c_road
     *  4. 2D_INTEGER_ARRAY cities
     */

    public static long roadsAndLibraries(int n, int c_lib, int c_road, List<List<Integer>> cities) {
        // Write your code here
        final List<List<Integer>> partition = makePartition(n, cities);
        long cost = 0;
        for (List<Integer> connexGraph : partition) {
            if (connexGraph.size() * c_lib < c_lib + (connexGraph.size() - 1) * c_road) {
                cost += (long) connexGraph.size() * c_lib;
            } else {
                cost += c_lib + (long) (connexGraph.size() - 1) * c_road;
            }
        }

        return cost;
    }

    public static List<List<Integer>> makePartition(int n, List<List<Integer>> cities) {
        final List<List<Integer>> partition = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            final int ii = i;
            final List<Integer> adjacents = cities
                    .stream()
                    .filter(it -> it.get(0) == ii || it.get(1) == ii)
                    .map(it -> it.get(0) == ii ? it.get(1) : it.get(0))
                    .collect(Collectors.toList());
            boolean found = false;
            for (List<Integer> subGraphNodes : partition) {
                if (adjacents.stream().anyMatch(subGraphNodes::contains)) {
                    subGraphNodes.add(i);
                    found = true;
                }
            }
            if (!found) {
                final List<Integer> singleton = new ArrayList<>();
                singleton.add(i);
                partition.add(singleton);
            }
        }
        return partition;
    }


}