Problem:Given a directed graph you need to complete the function topoSort which returns an array having the topologically sorted elements of the array and takes two arguments.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
//http://www.practice.geeksforgeeks.org/problem-page.php?pid=700255 /* You need to complete this function */ int * topoSort(vector<int> graph[], int N) { // Your code here vector<int> indeg(N,0); int *arr=(int*)malloc(sizeof(int)*N); queue<int> cue; int u,v; int idx=0; for(int i=0;i<N;i++) { for(int j=0;j<graph[i].size();j++) { indeg[graph[i][j]]+=1; } } for(int i=0;i<N;i++) { if(indeg[i]==0) cue.push(i); } while(cue.size()) { u=cue.front(); cue.pop(); arr[idx++]=u; for(int i=0;i<graph[u].size();i++) { v=graph[u][i]; indeg[v]-=1; if(indeg[v]==0) cue.push(v); } } return arr; } |