Topological sort | GeeksForGeeks Problem of the Day | 1 June

 Given a Directed Acyclic Graph (DAG) with V vertices and E edges, Find any Topological Sorting of that Graph.

Example 1:

Input:

Output:
1
Explanation:
The output 1 denotes that the order is
valid. So, if you have, implemented
your function correctly, then output
would be 1 for all test cases.
One possible Topological order for the
graph is 3, 2, 1, 0.

Example 2:

Input:

Output:
1
Explanation:
The output 1 denotes that the order is
valid. So, if you have, implemented
your function correctly, then output
would be 1 for all test cases.
One possible Topological order for the
graph is 5, 4, 2, 1, 3, 0.

Your Task:
You don't need to read input or print anything. Your task is to complete the function topoSort()  which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns an array consisting of the vertices in Topological order. As there are multiple Topological orders possible, you may return any of them. If your returned topo sort is correct then the console output will be 1 else 0.

Expected Time Complexity: O(V + E).
Expected Auxiliary Space: O(V).

Constraints:
2 ≤ V ≤ 104
1 ≤ E ≤ (N*(N-1))/2


SOLUTION = 

//{ Driver Code Starts

#include <bits/stdc++.h>

using namespace std;


// } Driver Code Ends

class Solution

{

public:

//Function to return list containing vertices in Topological order. 

void recur(int i, vector<int>&vis, stack<int> &st, vector<int> adj[]){

    vis[i] = 1;

    for(auto &it : adj[i]){

        if(!vis[it]){

            recur(it, vis, st, adj);

            

        }

    }

    st.push(i);

}

vector<int> topoSort(int V, vector<int> adj[]) 

{

    // code here

    vector<int>vis(V, 0);

    stack<int> st;

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

        if(!vis[i]){

            recur(i, vis, st, adj);

        }

    }

    vector<int> ans;

    while(!st.empty()){

        ans.push_back(st.top());

        st.pop();

    }

    return ans;

    

}

};


//{ Driver Code Starts.


/*  Function to check if elements returned by user

*   contains the elements in topological sorted form

*   V: number of vertices

*   *res: array containing elements in topological sorted form

*   adj[]: graph input

*/

int check(int V, vector <int> &res, vector<int> adj[]) {

    

    if(V!=res.size())

    return 0;

    

    vector<int> map(V, -1);

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

        map[res[i]] = i;

    }

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

        for (int v : adj[i]) {

            if (map[i] > map[v]) return 0;

        }

    }

    return 1;

}


int main() {

    int T;

    cin >> T;

    while (T--) {

        int N, E;

        cin >> E >> N;

        int u, v;


        vector<int> adj[N];


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

            cin >> u >> v;

            adj[u].push_back(v);

        }

        

        Solution obj;

        vector <int> res = obj.topoSort(N, adj);


        cout << check(N, res, adj) << endl;

    }

    

    return 0;

}

// } Driver Code Ends

Comments

Post a Comment

Popular posts from this blog

WAP to add or to multiply two matrices of order nXn.

#include <stdio.h> int main() {     // Write C code here     int n1, n2, i, j, m1[10][10], m2[10][10], sum[10][10], mul[10][10], k;     printf("Enter the order of the matrix: ");     scanf("%d%d", &n1, &n2);     printf("Enter the elements of the 1st matrix: ");     for (i=0; i<n1; i++) {         for (j=0; j<n2; j++) {             scanf("%d", &m1[i][j]);         }     }     printf("Enter the elements of the 2st matrix: ");     for (i=0; i<n1; i++) {         for (j=0; j<n2; j++) {             scanf("%d", &m2[i][j]);         }     }     for (i=0; i...
Read more

WAP that inputs two arrays and saves sum of corresponding elements of these arrays in a third array

  #include <stdio.h> int main() {     int a[50], b[50], sum[50], i, n;     printf("Enter the Elements in an array: ");     scanf("%d", &n);     printf("Enter the Elements of 1st array: ");     for (i=0; i<n; i++)     scanf("%d", &a[i]);     printf("Enter the Elements of 2nd array: ");     for (i=0; i<n; i++)     scanf("%d", &b[i]);     for (i=0; i<n; i++)     sum[i] = a[i] + b[i];          printf("Sum of the corresponding element of 1st and 2nd array is ", sum[i]);     for (i=0; i<n; i++)     printf("%d,", sum[i]);     return 0; }
Read more

WAP to find the minimum and maximum element of the array by using functions.

  #include <stdio.h> int max(int arr[], int n) {     int max = arr[0];     for(int i=0; i<n; i++) {         if (max < arr[i])         max = arr[i];     }     return max; } int min(int arr[], int n) {     int min = arr[0];     for(int i=0; i<n; i++) {         if (min > arr[i])         min = arr[i];     }     return min; } int main() {     int n, arr[50], i;     printf("Enter the number of element in an array: ");     scanf("%d", &n);     printf("Enter the elements in the array: ");     for (i=0; i<n; i++)     scanf("%d", &arr[i]);     printf("The maximum element of array is %d\nThe minimum elemen...
Read more