123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
#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 if all
the tasks can be finished */
bool canFinish(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, return false */
if(topo.size() < N) return false;
// Return true otherwise
return true;
}
};
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 if
all the tasks can be finished */
bool ans = sol.canFinish(N, arr);
// Output
if(ans)
cout << "All the tasks can be finished.";
else
cout << "All the tasks can not be finished.";
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
import java.util.*;
class Solution {
/* Function to return the topological
sorting of given graph */
private int[] topoSort(int V,
ArrayList<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 if all
the tasks can be finished */
public boolean canFinish(int N, int[][] arr) {
// To store the graph
ArrayList<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, return false */
if(topo.length < N) return false;
// Return true otherwise
return true;
}
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 if
all the tasks can be finished */
boolean ans = sol.canFinish(N, arr);
// Output
if(ans)
System.out.println("All the tasks can be finished.");
else
System.out.println("All the tasks can not be finished.");
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495
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 if all
# the tasks can be finished
def canFinish(self, N, arr):
# To store the graph
adj = [[] for _ in range(N)]
# Form the graph
for it in arr:
u = it[0]
v = it[1]
# 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, return false
if len(topo) < N:
return False
# Return true otherwise
return True
# Example usage
N = 4
arr = [
[1, 0],
[2, 1],
[3, 2]
]
sol = Solution()
ans = sol.canFinish(N, arr)
# Output
if ans:
print("All the tasks can be finished.")
else:
print("All the tasks can not be finished.")
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899
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 if all
the tasks can be finished */
canFinish(N, arr) {
// To store the graph
let adj = new Array(N).fill().map(() => []);
// Form the graph
for(let it of arr) {
let u = it[0];
let v = it[1];
// 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, return false */
if(topo.length < N) return false;
// Return true otherwise
return true;
}
}
// Example usage
const N = 4;
const arr = [
[1, 0],
[2, 1],
[3, 2]
];
const sol = new Solution();
const ans = sol.canFinish(N, arr);
// Output
if(ans)
console.log("All the tasks can be finished.");
else
console.log("All the tasks can not be finished.");
