Solution

This problem is similar to Tasks Scheduling, the only difference being that we need to find the best ordering of tasks so that it is possible to schedule them all.

Step-by-step Algorithm

1. Initialize the Graph:

   • Create a HashMap inDegree to count the incoming edges for every vertex.
   • Create a HashMap graph to represent the adjacency list of the graph.

2. Build the Graph:

   • For each task, set the initial in-degree to 0 and create an empty adjacency list.
   • For each prerequisite pair [parent, child]:
     • Add child to the adjacency list of parent.
     • Increment the in-degree of child by 1.

3. Find All Sources:

   • Initialize a queue sources and add all vertices with 0 in-degrees.

4. Sort Tasks:

   • While sources is not empty:
     • Remove a source from the queue, add it to sortedOrder.
     • For each child of this source:
       • Decrement the child's in-degree by 1.
       • If the child's in-degree becomes 0, add it to the sources queue.

5. Check for Cyclic Dependencies:

   • If the size of sortedOrder is not equal to the number of tasks, return an empty list (indicating a cycle).
   • Otherwise, return sortedOrder.

Algorithm Walkthrough

Given:

• Tasks = 6
• Prerequisites = [2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]

1. Initialize:

   • inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0}
   • graph = {0: [], 1: [], 2: [], 3: [], 4: [], 5: []}

2. Build the Graph:

   • For [2, 5]:
     • graph[2].append(5) → graph = {0: [], 1: [], 2: [5], 3: [], 4: [], 5: []}
     • inDegree[5]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 1}
   • For [0, 5]:
     • graph[0].append(5) → graph = {0: [5], 1: [], 2: [5], 3: [], 4: [], 5: []}
     • inDegree[5]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 2}
   • For [0, 4]:
     • graph[0].append(4) → graph = {0: [5, 4], 1: [], 2: [5], 3: [], 4: [], 5: []}
     • inDegree[4]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 2}
   • For [1, 4]:
     • graph[1].append(4) → graph = {0: [5, 4], 1: [4], 2: [5], 3: [], 4: [], 5: []}
     • inDegree[4]++ → inDegree = {0: 0, 1: 0, 2: 0, 3: 0, 4: 2, 5: 2}
   • For [3, 2]:
     • graph[3].append(2) → graph = {0: [5, 4], 1: [4], 2: [5], 3: [2], 4: [], 5: []}
     • inDegree[2]++ → inDegree = {0: 0, 1: 0, 2: 1, 3: 0, 4: 2, 5: 2}
   • For [1, 3]:
     • graph[1].append(3) → graph = {0: [5, 4], 1: [4, 3], 2: [5], 3: [2], 4: [], 5: []}
     • inDegree[3]++ → inDegree = {0: 0, 1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

3. Find All Sources:

   • Sources are tasks with 0 in-degrees: sources = [0, 1]

4. Process Each Source:

   • Process 0:
     • Remove 0 from sources → sources = [1]
     • Add 0 to sortedOrder → sortedOrder = [0]
     • For child 5 of 0, decrement inDegree[5] → inDegree[5] = 1
     • For child 4 of 0, decrement inDegree[4] → inDegree[4] = 1
   • Process 1:
     • Remove 1 from sources → sources = []
     • Add 1 to sortedOrder → sortedOrder = [0, 1]
     • For child 4 of 1, decrement inDegree[4] → inDegree[4] = 0 → Add 4 to sources → sources = [4]
     • For child 3 of 1, decrement inDegree[3] → inDegree[3] = 0 → Add 3 to sources → sources = [4, 3]
   • Process 4:
     • Remove 4 from sources → sources = [3]
     • Add 4 to sortedOrder → sortedOrder = [0, 1, 4]
   • Process 3:
     • Remove 3 from sources → sources = []
     • Add 3 to sortedOrder → sortedOrder = [0, 1, 4, 3]
     • For child 2 of 3, decrement inDegree[2] → inDegree[2] = 0 → Add 2 to sources → sources = [2]
   • Process 2:
     • Remove 2 from sources → sources = []
     • Add 2 to sortedOrder → sortedOrder = [0, 1, 4, 3, 2]
     • For child 5 of 2, decrement inDegree[5] → inDegree[5] = 0 → Add 5 to sources → sources = [5]
   • Process 5:
     • Remove 5 from sources → sources = []
     • Add 5 to sortedOrder → sortedOrder = [0, 1, 4, 3, 2, 5]

5. Check for Cyclic Dependencies:

   • sortedOrder = [0, 1, 4, 3, 2, 5] contains all tasks.

• Final order of tasks: [0, 1, 4, 3, 2, 5]

Code

Here is what our algorithm will look like: