Preference List
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
|
|
|