import java.util.*;

public class taskByLevel {

// 在这里构建有向图的时候，是 parent : list of children(对于数字，可以直接构造list of lists.对于String, 用map)

// 但是昨天那道题就明显是 child : list of parents更好用

/*
 算task和pretask輸出task by level的那題.

Just calculate indegree, bfs


input = {
{"cook", "eat"},   // do "cook" before "eat" 
{"study", "eat"},
{"sleep", "study"}}



output = (steps of a workflow):
{{"sleep", "cook"},.
{"study"},
{"eat"}}

step1: hashmap use integers to present tasks

step2: build the directed graph and record indegree

step3: topological sort(BFS)

* */

public static void main(String[] args){

String[][] tasks = {{"cook","eat"},{"study", "eat"}, {"sleep","study"}};

System.out.println(level(tasks));

}

public static List<List<String>> level(String[][] tasks){

// res

List<List<String>> res = new ArrayList<>();

// build the directed graph, and an indegree map

// map: parent: its children

Map<String, List<String>> map = new HashMap<>();

Map<String, Integer> indegree = new HashMap<>();

for(String[] task : tasks){

// task[0]: parent, task[1]: child

map.putIfAbsent(task[0], new ArrayList<>());

map.putIfAbsent(task[1], new ArrayList<>());

map.get(task[0]).add(task[1]);

// indegree map

indegree.putIfAbsent(task[0], 0);

indegree.putIfAbsent(task[1], 0);

indegree.put(task[1], indegree.get(task[1])+1);

}

//BFS, Starting from nodes whose indegree is 0

Queue<String> queue = new LinkedList<>();

for(Map.Entry<String, Integer> entry: indegree.entrySet()){

if(entry.getValue()==0) queue.add(entry.getKey());

}

while(!queue.isEmpty()){

int size = queue.size();

// traverse current level

List<String> cur = new ArrayList<>();

for(int i = 0; i < size; i++){

String parent = queue.remove();

cur.add(parent);

//indegree.remove(parent);

for(String child : map.get(parent)){

indegree.put(child, indegree.get(child)-1);

if(indegree.get(child) == 0) queue.add(child);

}

}

res.add(new ArrayList<>(cur));

}

return res;

}

}