123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/* Function to return the topological
sorting of given graph */
vector<int> topoSort(int V, vector<int> adj[]) {
// To store the In-degrees of nodes
vector<int> inDegree(V, 0);
// Update the in-degrees of nodes
for (int i = 0; i < V; i++) {
for(auto it : adj[i]) {
// Update the in-degree
inDegree[it]++;
}
}
// To store the result
vector<int> ans;
// Queue to facilitate BFS
queue<int> q;
// Add the nodes with no in-degree to queue
for(int i=0; i<V; i++) {
if(inDegree[i] == 0) q.push(i);
}
// Until the queue is empty
while(!q.empty()) {
// Get the node
int node = q.front();
// Add it to the answer
ans.push_back(node);
q.pop();
// Traverse the neighbours
for(auto it : adj[node]) {
// Decrement the in-degree
inDegree[it]--;
/* Add the node to queue if
its in-degree becomes zero */
if(inDegree[it] == 0) q.push(it);
}
}
// Return the result
return ans;
}
public:
/* Function to determine order
of tasks to finish all tasks */
vector<int> findOrder(int N, vector<vector<int>> arr) {
// To store the graph
vector<int> adj[N];
// Form the graph
for(auto it : arr) {
int u = it[0];
int v = it[1];
// Add the edge v-> u
adj[v].push_back(u);
}
// Get the topological ordering of graph
vector<int> topo = topoSort(N, adj);
/* If it doesn't contain all nodes,
it is impossible to finish all tasks */
if(topo.size() < N) return {};
// Return the ordering otherwise
return topo;
}
};
int main() {
int N = 4;
vector<vector<int>> arr = {
{1,0},
{2,1},
{3,2}
};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to determine order
of tasks to finish all tasks */
vector<int> ans = sol.findOrder(N, arr);
// Output
cout << "The order to perform tasks is:\n";
for(int i=0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
import java.util.*;
class Solution {
/* Function to return the topological
sorting of given graph */
private int[] topoSort(int V, List<Integer>[] adj) {
// To store the In-degrees of nodes
int[] inDegree = new int[V];
// Update the in-degrees of nodes
for (int i = 0; i < V; i++) {
for (int it : adj[i]) {
// Update the in-degree
inDegree[it]++;
}
}
// To store the result
int[] ans = new int[V];
int idx = 0;
// Queue to facilitate BFS
Queue<Integer> q = new LinkedList<>();
// Add the nodes with no in-degree to queue
for (int i = 0; i < V; i++) {
if (inDegree[i] == 0) q.add(i);
}
// Until the queue is empty
while (!q.isEmpty()) {
// Get the node
int node = q.poll();
// Add it to the answer
ans[idx++] = node;
// Traverse the neighbours
for (int it : adj[node]) {
// Decrement the in-degree
inDegree[it]--;
/* Add the node to queue if
its in-degree becomes zero */
if (inDegree[it] == 0) q.add(it);
}
}
// Return the result
return Arrays.copyOfRange(ans, 0, idx);
}
/* Function to determine order
of tasks to finish all tasks */
public int[] findOrder(int N, int[][] arr) {
// To store the graph
List<Integer>[] adj = new ArrayList[N];
for (int i = 0; i < N; i++) adj[i] = new ArrayList<>();
// Form the graph
for (int[] it : arr) {
int u = it[0];
int v = it[1];
// Add the edge v-> u
adj[v].add(u);
}
// Get the topological ordering of graph
int[] topo = topoSort(N, adj);
/* If it doesn't contain all nodes,
it is impossible to finish all tasks */
if (topo.length < N) return new int[0];
// Return the ordering otherwise
return topo;
}
public static void main(String[] args) {
int N = 4;
int[][] arr = {
{1, 0},
{2, 1},
{3, 2}
};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to determine order
of tasks to finish all tasks */
int[] ans = sol.findOrder(N, arr);
// Output
System.out.println("The order to perform tasks is:");
for (int i : ans) {
System.out.print(i + " ");
}
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889
from collections import deque
class Solution:
# Function to return the topological
# sorting of given graph
def topoSort(self, V, adj):
# To store the In-degrees of nodes
inDegree = [0] * V
# Update the in-degrees of nodes
for i in range(V):
for it in adj[i]:
# Update the in-degree
inDegree[it] += 1
# To store the result
ans = []
# Queue to facilitate BFS
q = deque()
# Add the nodes with no in-degree to queue
for i in range(V):
if inDegree[i] == 0:
q.append(i)
# Until the queue is empty
while q:
# Get the node
node = q.popleft()
# Add it to the answer
ans.append(node)
# Traverse the neighbours
for it in adj[node]:
# Decrement the in-degree
inDegree[it] -= 1
# Add the node to queue if its in-degree becomes zero
if inDegree[it] == 0:
q.append(it)
# Return the result
return ans
# Function to determine order
# of tasks to finish all tasks
def findOrder(self, N, arr):
# To store the graph
adj = [[] for _ in range(N)]
# Form the graph
for u, v in arr:
# Add the edge v-> u
adj[v].append(u)
# Get the topological ordering of graph
topo = self.topoSort(N, adj)
# If it doesn't contain all nodes,
# it is impossible to finish all tasks
if len(topo) < N:
return []
# Return the ordering otherwise
return topo
# Example usage
N = 4
arr = [
[1, 0],
[2, 1],
[3, 2]
]
sol = Solution()
# Function call to determine order
# of tasks to finish all tasks
ans = sol.findOrder(N, arr)
# Output
print("The order to perform tasks is:")
print(" ".join(map(str, ans)))
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697
class Solution {
/* Function to return the topological
sorting of given graph */
topoSort(V, adj) {
// To store the In-degrees of nodes
let inDegree = new Array(V).fill(0);
// Update the in-degrees of nodes
for (let i = 0; i < V; i++) {
for (let it of adj[i]) {
// Update the in-degree
inDegree[it]++;
}
}
// To store the result
let ans = [];
// Queue to facilitate BFS
let q = [];
// Add the nodes with no in-degree to queue
for (let i = 0; i < V; i++) {
if (inDegree[i] == 0) q.push(i);
}
// Until the queue is empty
while (q.length > 0) {
// Get the node
let node = q.shift();
// Add it to the answer
ans.push(node);
// Traverse the neighbours
for (let it of adj[node]) {
// Decrement the in-degree
inDegree[it]--;
/* Add the node to queue if
its in-degree becomes zero */
if (inDegree[it] == 0) q.push(it);
}
}
// Return the result
return ans;
}
/* Function to determine order
of tasks to finish all tasks */
findOrder(N, arr) {
// To store the graph
let adj = new Array(N).fill().map(() => []);
// Form the graph
for (let [u, v] of arr) {
// Add the edge v-> u
adj[v].push(u);
}
// Get the topological ordering of graph
let topo = this.topoSort(N, adj);
/* If it doesn't contain all nodes,
it is impossible to finish all tasks */
if (topo.length < N) return [];
// Return the ordering otherwise
return topo;
}
}
// Example usage
const N = 4;
const arr = [
[1, 0],
[2, 1],
[3, 2]
];
const sol = new Solution();
/* Function call to determine order
of tasks to finish all tasks */
const ans = sol.findOrder(N, arr);
// Output
console.log("The order to perform tasks is:");
console.log(ans.join(" "));
