Run Code  | API  | Code Wall  | Misc  | Feedback  | Login  | Theme  | Privacy  | Patreon 

Preference List

//'main' method must be in a class 'Rextester'.
//Compiler version 1.8.0_111

import java.util.*;
import java.lang.*;

class Rextester {

    public static void main(String args[]) {
        List<List<Integer>> input = new ArrayList<>();
        input.add(Arrays.asList(3, 5, 7, 9));
        input.add(Arrays.asList(2, 3, 8));
        input.add(Arrays.asList(5,8));
        System.out.println(input.toString());
        System.out.println(getPreference(input).toString());
    }
    
    public static List<Integer> getPreference(List<List<Integer>> prefers) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        for (List<Integer> prefer: prefers) {
            for (int i = 0; i < prefer.size(); i++) {
                if (!graph.containsKey(prefer.get(i))) graph.put(prefer.get(i), new HashSet<>());
                if (i + 1 < prefer.size()) graph.get(prefer.get(i)).add(prefer.get(i + 1));
            }
        }
        LinkedList<Integer> res = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        for (int i: graph.keySet()) DFS(graph, visited, i, res);
        return res;
    }

    public static void DFS(Map<Integer, Set<Integer>> graph, Set<Integer> visited, int i, LinkedList<Integer> res) {
        if (!visited.add(i)) return;
        for (int j: graph.get(i)) DFS(graph, visited, j, res);
        res.addFirst(i);
    }
}
 run  | edit  | history  | help 0